CiteSeerX Scientific Literature Digital Library and Search Engine
(3,644,890 recursos)
CiteSeerX is a scientific literature digital library and search engine that focuses primarily on the literature in computer and information science. CiteSeerx aims to improve the dissemination of scientific literature and to provide improvements in functionality, usability, availability, cost, comprehensiveness, efficiency, and timeliness in the access of scientific and scholarly knowledge

4.
A Survey of Program Slicing Techniques - Frank Tip
A program slice consists of the parts of a program that (potentially) affect the values computed at some point of interest. Such a point of interest is referred to as a slicing criterion, and is typically specified by a location in the program in combination with a subset of the program’s variables. The task of computing program slices is called program slicing. The original definition of a program slice was presented by Weiser in 1979. Since then, various slightly different notions of program slices have been proposed, as well as a number of methods to compute them. An important distinction...

6.
Running Time Analysis of a Multiobjective Evolutionary Algorithm on Simple and Hard Problems - Rajeev Kumar; Nilanjan Banerjee
In this paper, we suggest a multiobjective evolutionary algorithm based on a restricted mating pool (REMO) with a separate archive for storing the remaining population. Such archive based algorithms have been used for solving real-world applications, however, no theoretical results are available. In this paper, we present a rigorous running time complexity analysis for the algorithm on two simple discrete pseudo boolean functions and on the multiobjective knapsack problem which is known to be NP-complete. We use two well known simple functions LOTZ (Leading Zeros: Trailing Ones) and a quadratic function. For the knapsack problem we formalize a (1 +...

7.
Distributed hybrid genetic programming for learning boolean functions - Stefan Droste; Dominic Heutelbeck; Ingo Wegener
When genetic programming (GP) is used to find programs with Boolean inputs and outputs, ordered binary decision diagrams (OB-DDs) are often used successfully. In all known OBDD-based GP-systems the variable ordering, a crucial factor for the size of OBDDs, is preset to an optimal ordering of the known test function.Certainly this cannot be done in practical applications, where the function to learn and hence its optimal variable ordering are unknown. Here, the first GP-system is presented that evolves the variable ordering of the OBDDs and the OBDDs itself by using a distributed hybrid approach.For the experiments presented the unavoidable size...

8.
In Regression Testing without Code - JIANG ZHENG
Software products are often built from commercial-off-the-shelf (COTS) components. When new releases of these components are made available for integration and testing, source code is usually not provided by the COTS vendors. Various regression test selection techniques have been developed and have been shown to be cost effective. However, the majority of these test selection techniques rely on source code for change identification and impact analysis. This dissertation presents a regression test selection (RTS) process called Integrated- Black-box Approach for Component Change Identification (I-BACCI) for COTS-based applications. The I-BACCI process reduces the test suite based upon changes in the binary...

11.
Probabilistic Analysis of Knapsack Core Algorithms - Rene Beier; Berthold Vöcking
We study the average-case performance of algorithms for the binary knapsack problem. Our focus lies on the analysis of so-called core algorithms, the predominant algorithmic concept used in practice. These algorithms start with the computation of an optimal fractional solution that has only one fractional item and then they exchange items until an optimal integral solution is found. The idea is that in many cases the optimal integral solution should be close to the fractional one such that only a few items need to be exchanged. Despite the well known hardness of the knapsack problem on worst-case instances, practical studies...

12.
Distributed hybrid genetic programming for learning boolean functions - Stefan Droste; Dominic Heutelbeck; Ingo Wegener
When genetic programming (GP) is used to find programs with Boolean inputs and outputs, ordered binary decision diagrams (OB-DDs) are often used successfully. In all known OBDD-based GP-systems the variable ordering, a crucial factor for the size of OBDDs, is preset to an optimal ordering of the known test function. Certainly this cannot be done in practical applications, where the function to learn and hence its optimal variable ordering are unknown. Here, the first GP-system is presented that evolves the variable ordering of the OBDDs and the OBDDs itself by using a distributed hybrid approach. For the experiments presented the...

13.
Pricing for customers with probabilistic valuations as a continuous knapsack problem - Michael Benisch, et al.
In this paper, we examine the problem of choosing discriminatory prices for customers with probabilistic valuations and a seller with indistinguishable copies of a good. We show that under certain assumptions this problem can be reduced to the continuous knapsack problem (CKP). We present a new fast ǫ-optimal algorithm for solving CKP instances with asymmetric concave reward functions. We also show that our algorithm can be extended beyond the CKP setting to handle pricing problems with overlapping goods (e.g.goods with common components or common resource requirements), rather than indistinguishable goods. We provide a framework for learning distributions over customer valuations...

14.
Exploiting Symmetry in Multiple Knapsack Problems - Alex S. Fukunaga
The multiple knapsack problem (MKP) is a classical combinatorial optimization problem. A recent algorithm for some classes of the MKP is bincompletion, a bin-oriented, branch-and-bound algorithm. We investigate mechanisms for detecting and breaking symmetry in the bin-completion search space. We propose path-symmetry and pathdominance, two new symmetry relations which are more powerful generalization of previous MKP symmetry breaking techniques. Experiments show that path-symmetry and path-dominance significantly reduce the number of nodes searched by bin-completion. In particular, a variant of pathsymmetry is shown to significantly improve upon the previous state of the art for the MKP with respect to both runtime...

15.
Expected Runtimes of a Simple Multi-objective Evolutionary Algorithm - Oliver Giel
The expected runtime of a simple multiobjective evolutionary algorithm for the Boolean decision space is analyzed. The algorithm uses independent bit flips as mutation operator and, therefore, searches globally. It is proved that the expected runtime is O(n n) for all objective functions {0, 1} n → m. This worstcase bound is tight and matches the worst-case bounds for fundamental evolutionary algorithms working in the scenario of single-objective optimization. For the bicriteria problem LOTZ (Leading Ones Trailing Zeroes), it is shown that the expected runtime is O(n³). Moreover, the runtime is O(n³) with an overwhelming probability. Finally, the function...

16.
Cooperative Strategies for Solving the Bicriteria Sparse Multiple Knapsack Problem - F. Sibel Salman; Jayant R. Kalagnanam , Sesh Murthy
For hard optimization problems, it is difficult to design heuristic algorithms which exhibit uniformly superior performance for all problem instances. As a result it becomes necessary to tailor the algorithms based on the problem instance. In this paper, we introduce the use of a cooperative problem solving team of heuristics that evolves algorithms for a given problem instance. The efficacy of this method is examined by solving six difficult instances of a bicriteria sparse multiple knapsack problem. Results indicate that such tailored algorithms uniformly improve solutions as compared to using predesigned heuristic algorithms.

17.
Semantics Guided Regression Test Cost Reduction - David Binkley
Software maintainers are faced with the task of regression testing: retesting a modified program on an often large number of test cases. The cost of regression testing can be reduced if the size of the program that must be retested is reduced and if old test cases and old test results can be reused. Tw o complimentary algorithms for reducing the cost of regression testing are presented. The first produces a program called differences that captures the semantic change between certified, apreviously tested program, and modified, achanged version of certified. Itis more efficient to test differences, because it omits unchanged...

18.
Hybrid Rounding Techniques for Knapsack Problems - Monaldo Mastrolilli; Marcus Hutter
We address the classical knapsack problem and a variant in which an upper bound is imposed on the number of items that can be selected. We show that appropriate combinations of rounding techniques yield novel and powerful ways of rounding. As an application of these techniques, we present a linear-storage Polynomial Time Approximation Scheme (PTAS) and a Fully Polynomial Time Approximation Scheme (FPTAS) that compute an approximate solution, of any fixed accuracy, in linear time. This linear complexity bound gives a substantial improvement of the best previously known polynomial bounds [2].

20.
The Reactive Tabu Search - Roberto Battiti; Giampietro Tecchiolli
this paper the concept of chaotic attractor is used only as an example of a dynamic behavior that could affect the search process, we summarize the main characteristics and refer to [13] for a detailed theoretical analysis. Chaotic attractors are characterized by a "contraction of the areas", so that trajectories starting with different initial conditions will be compressed in a limited area of the configuration space, and by a "sensitive dependence upon the initial conditions", so that different trajectories will diverge. For an analytical characterization of this sensitive dependence, it is convenient to introduce the concept of Lyapunov exponent. Let...