greedy algorithms are among the most elementary ones in theoretical computer science and understanding the conditions under which they yield an optimum solution is a widely studied problem. Greedoids were introduced b...
详细信息
greedy algorithms are among the most elementary ones in theoretical computer science and understanding the conditions under which they yield an optimum solution is a widely studied problem. Greedoids were introduced by Korte and Lovasz at the beginning of the 1980s as a generalization of matroids. One of the basic motivations of the notion was to extend the theoretical background behind greedy algorithms beyond the well-known results on matroids. Indeed, many well-known algorithms of a greedy nature that cannot be interpreted in a matroid-theoretical context are special cases of the greedy algorithm on greedoids. Although this algorithm turns out to be optimal in surprisingly many cases, no general theorem is known that explains this phenomenon in all these cases. Furthermore, certain claims regarding this question that were made in the original works of Korte and Lovasz turned out to be false only most recently. The aim of this paper is to revisit and straighten out this question: we summarize recent progress and we also prove new results in this field. In particular, we generalize a result of Korte and Lovasz and thus we obtain a sufficient condition for the optimality of the greedy algorithm that covers a much wider range of known applications than the original one.
This paper presents a greedy algorithm for decomposing convex structuring elements as sequence of Minkowski additions of subsets of the elementary square (i.e., the 3 x 3 square centered at the origin). The technique ...
详细信息
This paper presents a greedy algorithm for decomposing convex structuring elements as sequence of Minkowski additions of subsets of the elementary square (i.e., the 3 x 3 square centered at the origin). The technique proposed is very simple and it is based on algebraic and geometric properties of Minkowski additions. Besides its simplicity, the advantage of this new technique over other known algorithms is that it generates a minimal sequence of not necessarily convex subsets of the elementary square. Thus, subsets with smaller cardinality are generated and a faster implementation of the corresponding dilations and erosions can be achieved. Experimental results, proof of correctness and analysis of computational time complexity of the algorithm are also given.
In this paper a greedy algorithm for some variants of the sequencing by hybridization method is presented. In the standard version of the method information about repetitions is not available. In the paper it is assum...
详细信息
In this paper a greedy algorithm for some variants of the sequencing by hybridization method is presented. In the standard version of the method information about repetitions is not available. In the paper it is assumed that a partial information of this type is a part of the problem instance. Here two simple but realistic models of this information are taken into consideration. The first one assumes it is known if a given element of a spectrum appears in the target sequence once or more than once. The second model uses the knowledge if a given element of a spectrum occurs in the analyzed sequence once, twice or at least three times. The proposed greedy algorithm solves the variant of the problem with positive and negative errors. Results of a computational experiment are reported which, among others, confirm that the additional information leads to the improvement of the obtained solutions. They also show that the more precise model of information increases the quality of reconstructed sequences.
We show that for the vast majority of satisfiable 3CNF formulae, the local search heuristic that starts at a random truth assignment and repeatedly flips the variable that improves the number of satisfied clauses the ...
详细信息
We show that for the vast majority of satisfiable 3CNF formulae, the local search heuristic that starts at a random truth assignment and repeatedly flips the variable that improves the number of satisfied clauses the most, almost always succeeds in discovering a satisfying truth assignment.
We study a variation of the classical Shortest Common Superstring (SCS) problem in which a shortest superstring of a finite set of strings S is sought containing as a factor every string of S or its reversal. We call ...
详细信息
We study a variation of the classical Shortest Common Superstring (SCS) problem in which a shortest superstring of a finite set of strings S is sought containing as a factor every string of S or its reversal. We call this problem Shortest Common Superstring with Reversals (SCS-R). This problem has been introduced by Jiang et al. [9], who designed a greedy like algorithm with length approximation ratio 4. In this paper, we show that a natural adaptation of the classical greedy algorithm for SCS has (optimal) compression ratio 1, i.e., the sum of the overlaps in the output string is at least half the sum of the overlaps in an optimal solution. We also provide a linear-time implementation of our algorithm. (C) 2015 Elsevier B.V. All rights reserved.
With a widespread adoption of synthetic aperture radar (SAR) observations in Earth sciences, the volume of annual data updates has soared to petabyte scales. Consequently, the accurate retrieval and efficient storage ...
详细信息
With a widespread adoption of synthetic aperture radar (SAR) observations in Earth sciences, the volume of annual data updates has soared to petabyte scales. Consequently, the accurate retrieval and efficient storage of SAR data have become pressing concerns. The existing data searching method exhibits significant redundancy, leading to wasteful consumption of bandwidth and storage resources. Aiming to address this issue, we present here an optimized retrieval method grounded in a greedy algorithm, which can substantially reduce redundant data by approximately 20-65% while ensuring comprehensive data coverage over the areas of interest. By significantly minimizing redundant data, the proposed method markedly enhances data acquisition efficiency and conserves storage space. Validation experiments with Sentinel-1 data, employing various keyhole markup language scope files as inputs, affirm the effectiveness and reliability of the method. The application of the proposed method is expected to pave the way for efficient data management and fully automatic InSAR processing.
We consider hereditary systems (such as matroids) where the underlying elements have independent random costs, and investigate the cost of the base picked by the greedy algorithm.
We consider hereditary systems (such as matroids) where the underlying elements have independent random costs, and investigate the cost of the base picked by the greedy algorithm.
A bound on the performance of the greedy algorithm for finding the maximum of a submodular set function subject to a cardinality constraint is shown to apply to the problem of selecting a fixed number of events so tha...
详细信息
A bound on the performance of the greedy algorithm for finding the maximum of a submodular set function subject to a cardinality constraint is shown to apply to the problem of selecting a fixed number of events so that the probability that at least one of the selected events occurs is maximized. The bound is improved under an additional assumption which is plausible when the aim is to find a biologically active compound in pharmaceutical research.
This paper first introduces the fundamental principles of immune algorithm (IA), greedy algorithm (GA) and delete-cross operator (DO). Based on these basic algorithms, a hybrid immune algorithm (HIA) is constructed to...
详细信息
This paper first introduces the fundamental principles of immune algorithm (IA), greedy algorithm (GA) and delete-cross operator (DO). Based on these basic algorithms, a hybrid immune algorithm (HIA) is constructed to solve the traveling salesman problem (TSP). HIA employs GA to initialize the routes of TSP and utilizes DO to delete routes of crossover. With dynamic mutation operator (DMO) adopted to improve searching precision, this proposed algorithm can increase the likelihood of global optimum after the hybridization. Experimental results demonstrate that the HIA algorithm is able to yield a better solution than that of other algorithms, which also takes less computation time.
Computational calculations of combustion problems involving large numbers of species and reactions with a detailed description of the chemistry can be very expensive. Numerous dimension reduction techniques have been ...
详细信息
Computational calculations of combustion problems involving large numbers of species and reactions with a detailed description of the chemistry can be very expensive. Numerous dimension reduction techniques have been developed in the past to reduce the computational cost. In this paper, we consider the rate controlled constrained-equilibrium (RCCE) dimension reduction method, in which a set of constrained species is specified. For a given number of constrained species, the 'optimal' set of constrained species is that which minimizes the dimension reduction error. The direct determination of the optimal set is computationally infeasible, and instead we present a greedy algorithm which aims at determining a 'good' set of constrained species;that is, one leading to near-minimal dimension reduction error. The partially-stirred reactor (PaSR) involving methane premixed combustion with chemistry described by the GRI-Mech 1.2 mechanism containing 31 species is used to test the algorithm. Results on dimension reduction errors for different sets of constrained species are presented to assess the effectiveness of the greedy algorithm. It is shown that the first four constrained species selected using the proposed greedy algorithm produce lower dimension reduction error than constraints on the major species: CH4, O2, CO2 and H2O. It is also shown that the first ten constrained species selected using the proposed greedy algorithm produce a non-increasing dimension reduction error with every additional constrained species;and produce the lowest dimension reduction error in many cases tested over a wide range of equivalence ratios, pressures and initial temperatures.
暂无评论