Search

Submodular maximization is one of the central topics in combinatorial optimization. It has found numerous applications in the real world. In the past decades, a series of algorithms have been proposed for this problem. However, most of the state-of-the-art algorithms are randomized. There remain non-negligible gaps with respect to approximation ratios between deterministic and randomized algorithms in submodular maximization. In this paper, we propose deterministic algorithms with improved approximation ratios for non-monotone submodular maximization. Specifically, for the matroid constraint, we provide a deterministic 0.283 − o (1) approximation algorithm, while the previous best deterministic algorithm only achieves a 1/4 approximation ratio. For the knapsack constraint, we provide a deterministic 1/4 approximation algorithm, while the previous best deterministic algorithm only achieves a 1/6 approximation ratio. For the linear packing constraints with large widths, we provide a deterministic 1 / 6 − ϵ approximation algorithm. To the best of our knowledge, there is currently no deterministic approximation algorithm for the constraints. [ABSTRACT FROM AUTHOR]

In an inverse combinatorial optimization problem, a feasible solution is given and is not optimal under the current parameters. The aim is to make the feasible solution optimal by modifying the current parameters as little as possible. The modification cost can be measured by different norms, such as weighted l 1 norm, weighted l 2 norm, weighted l ∞ norm, weighted Hamming distance and so on. In this paper, we focus on the constrained inverse minimum flow problems under the weighted Hamming distance. Three different models are considered: the general problem under the weighted bottleneck-type Hamming distance and two cases under the mixed of sum-type and bottleneck type. Strongly polynomial algorithms are presented for the models we studied. [ABSTRACT FROM AUTHOR]

We propose a dynamic programming framework for an exact multi-stage (lexicographic) combinatorial optimization. Unlike conventional algorithms of dynamic programming that return one optimal solution, two dynamic programming algorithms proposed in this paper are coping with the whole set of optimal solutions or with its essential part. We describe the set of elements for optimization by a labeled directed acyclic graph, which in some sense, is similar to the structure of subproblems of the considered problem. For a given cost function (objective), the first algorithm constructs a subgraph of this graph that describes the whole set of optimal elements or its essential part. This algorithm can be used for multi-stage optimization of elements relative to a sequence of cost functions. The second algorithm counts elements before the optimization and after each optimization step. The considered labeled directed acyclic graph is a kind of circuit. This circuit builds the set of elements for optimization from one-element sets attached to input nodes. It uses the operation of union of sets attached to unifying nodes and functional operations attached to functional nodes. The algorithms for optimization and counting elements are defined for an arbitrary circuit without repetitions in which each element is generated exactly one time. For a considered problem with a known conventional dynamic programming solution algorithm, usually, it is easy to construct a corresponding circuit without repetitions. Once the circuit and cost functions are defined, our framework provides the correctness proofs and detailed time complexity analysis for the proposed algorithms. To make this approach more intuitive, we consider an illustrative example related to the maximum subarray problem. We tested our approach on the following nine combinatorial optimization problems: matrix chain multiplication, global sequence alignment, optimal paths in directed graphs, binary search trees, optimal bitonic tour, segmented least squares, convex polygon triangulation, one-dimensional clustering, and line breaking (text justification). We consider the last three problems in detail: construct a circuit without repetitions, describe at least two cost functions, evaluate a number of operations and time required by the algorithms, discuss an example, and consider the results of computer experiments with randomly generated instances of the problem. [ABSTRACT FROM AUTHOR]

Partitioning a network into k pieces is a fundamental problem in network science. A simple measure of partitioning a network is provided by the Max k -Uncut problem. Given an n -vertex undirected graph G with nonnegative weights defined on edges, and a positive integer k , the Max k -Uncut problem asks to find a k -partition of the vertices of G to maximize the total weight of edges that are not in the cut. This problem is the complement of the classic Min k -Cut problem, and has close relation to many combinatorial optimization problems, including the famous Densest k -Subgraph problem. In this paper, we propose a greedy approximation algorithm for the Max k -Uncut problem with performance ratio 1 − 2 (k − 1) n. The algorithm is very simple, which consists of only k − 1 min cut computations. The algorithm has fast running time O (k n 2) and is hence implementable. The experimental results show that the algorithm has excellent practical performance. [ABSTRACT FROM AUTHOR]

Popular matchings have been intensively studied recently as a relaxed concept of stable matchings. By applying the concept of popular matchings to branchings in directed graphs, Kavitha et al. introduced popular branchings. Let G = (V G , E G) be a directed graph, where each vertex has preferences over its incoming arcs, and B and B ′ be branchings in G. A vertex v ∈ V G prefers B to B ′ if v prefers its incoming arc of B to that of B ′ , where having an arbitrary incoming arc is preferred to having no incoming arc. We say that B is more popular than B ′ if the number of vertices preferring B to B ′ is greater than the number of vertices preferring B to B ′. A branching B is called a popular branching if there is no branching more popular than B. Kavitha et al. proposed an algorithm for finding a popular branching when the preferences of each vertex are given by a strict partial order. The correctness of this algorithm is proved by utilizing classical theorems on the duality of weighted arborescences. In this paper, we generalize popular branchings to weighted popular branchings in vertex-weighted directed graphs, in the same manner as weighted popular matchings by Mestre. We give an algorithm for finding a weighted popular branching for the case where the preferences of each vertex are given by a total preorder and the weights satisfy certain conditions. Our algorithm is based on Kavitha et al.'s algorithm, while it includes elaborated procedures resulting from the vertex-weights. Its correctness also builds upon the duality of weighted arborescences. [ABSTRACT FROM AUTHOR]

Abstract: The utilization of populations is one of the most important features of evolutionary algorithms (EAs). There have been many studies analyzing the impact of different population sizes on the performance of EAs. However, most of such studies are based on computational experiments, except for a few cases. The common wisdom so far appears to be that a large population would increase the population diversity and thus help an EA. Indeed, increasing the population size has been a commonly used strategy in tuning an EA when it did not perform as well as expected for a given problem. He and Yao (2002)  showed theoretically that for some problem instance classes, a population can help to reduce the runtime of an EA from exponential to polynomial time. This paper analyzes the role of population further in EAs and shows rigorously that large populations may not always be useful. Conditions, under which large populations can be harmful, are discussed in this paper. Although the theoretical analysis was carried out on one multimodal problem using a specific type of EAs, it has much wider implications. The analysis has revealed certain problem characteristics, which can be either the problem considered here or other problems, that lead to the disadvantages of large population sizes. The analytical approach developed in this paper can also be applied to analyzing EAs on other problems. [Copyright &y& Elsevier]

Abstract: In this paper the minimum spanning tree problem with uncertain edge costs is discussed. In order to model the uncertainty a discrete scenario set is specified and a robust framework is adopted to choose a solution. The min–max, min–max regret and 2-stage min–max versions of the problem are discussed. The complexity and approximability of all these problems are explored. It is proved that the min–max and min–max regret versions with nonnegative edge costs are hard to approximate within for any unless the problems in NP have quasi-polynomial time algorithms. Similarly, the 2-stage min–max problem cannot be approximated within unless the problems in NP have quasi-polynomial time algorithms. In this paper randomized LP-based approximation algorithms with performance bound of for min–max and 2-stage min–max problems are also proposed. [ABSTRACT FROM AUTHOR]

Abstract: Given an -vertex directed graph and a set of requests, we consider assigning a set of edges to each vertex in so that for every request in the union of the edge sets assigned to and contains a path from to . The Minimum Certificate Dispersal Problem (MCD) is defined as one to find an assignment that minimizes the sum of the cardinalities of the edge sets assigned to each vertex. This problem has been shown to be NP-hard in general, though it is polynomially solvable for some restricted classes of graphs and restricted request structures, such as bidirectional trees with requests of all pairs of vertices. In this paper, we give an advanced investigation about the difficulty of MCD by focusing on the relationship between its (in)approximability and request structures. We first show that MCD with general has lower and upper bounds on approximation ratio under the assumption . We then assume forms a clique structure, called Subset-Full, which is a natural setting in the context of the application. Interestingly, under this natural setting, MCD becomes 2-approximable, though it has still no polynomial time approximation algorithm whose factor is better than 677/676 unless . Finally, we show that this approximation ratio can be improved to 3/2 for the undirected variant of MCD with Subset-Full. [Copyright &y& Elsevier]

Abstract: Motivated by the constrained minimum spanning tree (CST) problem in Hassin and Levin [R. Hassin, A. Levin, An efficient polynomial time approximation scheme for the constrained minimum spanning tree problem using matroid intersection, SIAM Journal on Computing 33 (2) (2004) 261–268], we study a new combinatorial optimization problem in this paper, called the general subdivision-constrained spanning tree problem (GSCST): given a graph with two nonnegative integers and for each edge , two positive integers and , the GSCST problem is to first find a spanning tree of with weight and then to insert some new vertices on some suitable edges in such that each edge in the subdivision tree of has its weight not beyond . The objective is to minimize the cost of such new vertices inserted on the suitable edges among all spanning trees of subject to the two preceding constraints, where a subdivision tree of is constructed by inserting some new vertices on the suitable edges in , the value is the least number of vertices inserted and is the cost of each vertex inserted on the edge . We obtain the following main results: (1) the GSCST problem and its variant are still NP-hard, by a reduction from the 0–1 knapsack problem, respectively; (2) the GSCST problem as well as its variant is polynomially equivalent to the CST problem, which implies the existence of a polynomial time approximation scheme to solve the GSCST problem and its variant; (3) we finally design three strongly polynomial time algorithms to solve the special versions of the GSCST problem and its variant, respectively. [Copyright &y& Elsevier]

Abstract: The submodular function minimization problem (SFM) is a fundamental problem in combinatorial optimization and several fully combinatorial polynomial-time algorithms have recently been discovered to solve this problem. The most general versions of these algorithms are able to minimize any submodular function whose domain is a set of tuples over any totally-ordered finite set and whose range includes both finite and infinite values. In this paper we demonstrate that this general form of SFM is just one example of a much larger class of tractable discrete optimization problems defined by valued constraints. These tractable problems are characterized by the fact that their valued constraints have an algebraic property which we call a tournament pair multimorphism. This larger tractable class also includes the problem of satisfying a set of Horn clauses (Horn-SAT), as well as various extensions of this problem to larger finite domains. [Copyright &y& Elsevier]

Abstract: In this paper, we consider the role of the crossover operator in genetic algorithms. Specifically, we study optimisation problems that exhibit many local optima and consider how crossover affects the rate at which the population breaks the symmetry of the problem. As an example of such a problem, we consider the subset sum problem. In doing so, we demonstrate a previously unobserved phenomenon, whereby the genetic algorithm with crossover exhibits a critical mutation rate, at which its performance sharply diverges from that of the genetic algorithm without crossover. At this critical mutation rate, the genetic algorithm with crossover exhibits a rapid increase in population diversity. We calculate the details of this phenomenon on a simple instance of the subset sum problem and show that it is a classic phase transition between ordered and disordered populations. Finally, we show that this critical mutation rate corresponds to the transition between the genetic algorithm accelerating or preventing symmetry breaking and that the critical mutation rate represents an optimum in terms of the balance of exploration and exploitation within the algorithm. [Copyright &y& Elsevier]

Abstract: Multiobjective Evolutionary Algorithms (MOEAs) are increasingly being used for effectively solving many real-world problems, and many empirical results are available. However, theoretical analysis is limited to a few simple toy functions. In this work, we select the well-known knapsack problem for the analysis. The multiobjective knapsack problem in its general form is NP-complete. Moreover, the size of the set of Pareto-optimal solutions can grow exponentially with the number of items in the knapsack. Thus, we formalize a -approximate set of the knapsack problem and attempt to present a rigorous running time analysis of a MOEA to obtain the formalized set. The algorithm used in the paper is based on a restricted mating pool with a separate archive to store the remaining population; we call the algorithm a Restricted Evolutionary Multiobjective Optimizer (REMO). We also analyze the running time of REMO on a special bi-objective linear function, known as LOTZ (Leading Ones : Trailing Zeros), whose Pareto set is shown to be a subset of the knapsack. An extension of the analysis to the Simple Evolutionary Multiobjective Optimizer (SEMO) is also presented. A strategy based on partitioning of the decision space into fitness layers is used for the analysis. [Copyright &y& Elsevier]

Abstract: Trade-off (aka Pareto) curves are typically used to represent the trade-off among different objectives in multiobjective optimization problems. Although trade-off curves are exponentially large for typical combinatorial optimization problems (and infinite for continuous problems), it was observed in Papadimitriou and Yannakakis [On the approximability of trade-offs and optimal access of web sources, in: Proc. 41st IEEE Symp. on Foundations of Computer Science, 2000] that there exist polynomial size approximations for any , and that under certain general conditions, such approximate -Pareto curves can be constructed in polynomial time. In this paper we seek general-purpose algorithms for the efficient approximation of trade-off curves using as few points as possible. In the case of two objectives, we present a general algorithm that efficiently computes an -Pareto curve that uses at most 3 times the number of points of the smallest such curve; we show that no algorithm can be better than 3-competitive in this setting. If we relax to any , then we can efficiently construct an -curve that uses no more points than the smallest -curve. With three objectives we show that no algorithm can be c-competitive for any constant c unless it is allowed to use a larger value. We present an algorithm that is 4-competitive for any . We explore the problem in high dimensions and give hardness proofs showing that (unless P=NP) no constant approximation factor can be achieved efficiently even if we relax by an arbitrary constant. [Copyright &y& Elsevier]

Abstract: Research on a new metaheuristic for optimization is often initially focused on proof-of-concept applications. It is only after experimental work has shown the practical interest of the method that researchers try to deepen their understanding of the method''s functioning not only through more and more sophisticated experiments but also by means of an effort to build a theory. Tackling questions such as “how and why the method works’’ is important, because finding an answer may help in improving its applicability. Ant colony optimization, which was introduced in the early 1990s as a novel technique for solving hard combinatorial optimization problems, finds itself currently at this point of its life cycle. With this article we provide a survey on theoretical results on ant colony optimization. First, we review some convergence results. Then we discuss relations between ant colony optimization algorithms and other approximate methods for optimization. Finally, we focus on some research efforts directed at gaining a deeper understanding of the behavior of ant colony optimization algorithms. Throughout the paper we identify some open questions with a certain interest of being solved in the near future. [Copyright &y& Elsevier]

Local search has been widely used in combinatorial optimization (Local Search in Combinatorial Optimization, Wiley, New York, 1997), however, in the case of multicriteria optimization almost no results are known concerning the ability of local search algorithms to generate “good” solutions with performance guarantee. In this paper, we introduce such an approach for the classical traveling salesman problem (TSP) problem (Proc. STOC’00, 2000, pp. 126–133). We show that it is possible to get in linear time, a 3/2-approximate Pareto curve using an original local search procedure based on the 2-opt neighborhood, for the bicriteria TSP(1,2) problem where every edge is associated to a couple of distances which are either 1 or 2 (Math. Oper. Res. 18 (1) (1993) 1). [Copyright &y& Elsevier]