Search

In the directed Steiner tree (DST) problem, we are given an n-vertex directed edgeweighted graph, a root r, and a collection of k terminal nodes. Our goal is to find a minimum-cost subgraph that contains a directed path from r to every terminal. We present an O(log² k/ log log k)- approximation algorithm for DST that runs in quasi-polynomial time, i.e., in time n poly log(k) . By assuming the projection game conjecture and NP ¢n0<ε<1 ZPTIME(2nε ) and adjusting the parameters in the hardness result of [Halperin and Krauthgamer, Polylogarithmic inapproximability, in Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003, pp. 585--594], we show the matching lower bound of Ω (log² k/ log log k) for the class of quasi-polynomial time algorithms, meaning that our approximation ratio is asymptotically the best possible. Our algorithm is proceeded by reducing DST to an intermediate problem, namely, the group Steiner tree on trees with dependency constraint problem, which we approximate using the framework developed by [Rothvo{\ss}, Directed Steiner Tree and the Lasserre Hierarchy, preprint, arxiv:1111.5473, 2011] and [Friggstad et al., Linear programming hierarchies suffice for directed Steiner tree, in Proceedings of the 17th Annual Conference on Integer Programming and Combinatorial Optimization, 2014, pp. 285--296]. [ABSTRACT FROM AUTHOR]

Longest common subsequence (LCS) is one of the most fundamental problems in combinatorial optimization. Apart from theoretical importance, LCS has enormous applications in bioinformatics, revision control systems, and data comparison programs. Although a simple dynamic program computes LCS in quadratic time, it has been recently proven that the problem admits a conditional lower bound and may not be solved in truly subquadratic time [2, 18]. In addition to this, LCS is notoriously hard with respect to approximation algorithms. Apart from a trivial sampling technique that obtains an nx approximation solution in time O(n2-2x) nothing else is known for LCS. This is in sharp contrast to its dual problem edit distance, for which several linear time solutions were obtained in the past two decades [5, 6, 10, 11, 19]. In this work, we present the first nontrivial algorithm for approximating LCS in linear time. Our main result is a linear time algorithm for the LCS which has an approximation factor of O(n0.4991319) in expectation. This beats the √n barrier for approximating LCS in linear time. [ABSTRACT FROM AUTHOR]

Submodularity is one of the most important properties in combinatorial optimization, and k-submodularity is a generalization of submodularity. Maximization of a k-submodular function requires an exponential number of value oracle queries, and approximation algorithms have been studied. For unconstrained k-submodular maximization, Iwata, Tanigawa, and Yoshida, [Improved approximation algorithms for k-submodular function maximization, in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2016, pp. 404-413] gave a randomized k/(2k 1)-approximation algorithm for monotone functions and a randomized 1/2-approximation algorithm for nonmonotone functions. In this paper, we present improved randomized algorithms for nonmonotone functions. Our algorithm gives a k2+1 2k2+1 -approximation for k geq 3. We also give a randomized surd 17 3 2 -approximation algorithm for k = 3. We use the same framework used in Iwata, Tanigawa, and Yoshida, [Improved approximation algorithms for k-submodular function maximization, in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2016, pp. 404--413] and Ward and v Zivn'y [ACM Trans. Algorithms, 12 (2016), pp. 46:1--47:26] with different probabilities. [ABSTRACT FROM AUTHOR]

The Multiway-Cut problem is a fundamental graph partitioning problem in which the objective is to find a minimum weight set of edges disconnecting a given set of special vertices called terminals. This problem is NP-hard and there is a well-known geometric relaxation in which the graph is embedded into a high dimensional simplex. Rounding a solution to the geometric relaxation is equivalent to partitioning the simplex. We present a novel simplex partitioning algorithm which is based on two ingredients: competing exponential clocks and distortion. Unlike previous methods, it utilizes cuts that are not parallel to the faces of the simplex. Applying this partitioning algorithm to the multiway cut problem, we obtain a simple (4/3)-approximation algorithm, thus, improving upon the current best-known result. This bound is further pushed to obtain an approximation factor of 1.32388. It is known that under the assumption of the unique games conjecture, the best possible approximation for the Multiway-Cut problem can be attained via the geometric relaxation. [ABSTRACT FROM AUTHOR]

We propose an optimization model using a novel robust preference relationship| reference-based almost stochastic dominance (RSD). The concept of RSD addresses the two problems in utility-based decision making: (i) ambiguity and inaccuracy in characterizing the decision maker's individual risk attitude, and (ii) overconservativeness of stochastic dominance representing general properties of risk aversion. The RSD rule reveals the maximum dominance level quantifying the robustness of the decision maker's preference between alternative choices. We first develop an approximation model using Bernstein polynomials, show the asymptotic convergence of its optimal value and set of optimal solutions to their true counterparts as the degree of Bernstein polynomials increases, and analyze the convergence rate of its feasible region. We next develop a cut-generation algorithm to solve the approximation model. Finally, we further adapt this cut-generation algorithm to seek a valid option most robustly preferable to a random benchmark. The effectiveness and computational complexity of the model have been illustrated using a portfolio optimization problem. [ABSTRACT FROM AUTHOR]

We present an optimal, combinatorial 1-1/e approximation algorithm for monotone submodular optimization over a matroid constraint. Compared to the continuous greedy algorithm [G. Calinescu et al., IPCO, Springer, Berlin, 2007, pp. 182-196] our algorithm is extremely simple and requires no rounding. It consists of the greedy algorithm followed by a local search. Both phases are run not on the actual objective function, but on a related auxiliary potential function, which is also monotone and submodular. In our previous work on maximum coverage [Y. Filmus and J. Ward, FOCS, IEEE, Piscataway, NJ, 2012, pp. 659-668], the potential function gives more weight to elements covered multiple times. We generalize this approach from coverage functions to arbitrary monotone submodular functions. When the objective function is a coverage function, both definitions of the potential function coincide. Our approach generalizes to the case where the monotone submodular function has restricted curvature. For any curvature c, we adapt our algorithm to produce a (1-e-c)/c approximation. This matches results of Vondrák [STOC, ACM, New York, 2008, pp. 67-74], who has shown that the continuous greedy algorithm produces a (1 - e-c)/c approximation when the objective function has curvature c with respect to the optimum, and proved that achieving any better approximation ratio is impossible in the value oracle model. [ABSTRACT FROM AUTHOR]

A number of recent results on optimization problems involving submodular functions have made use of the multilinear relaxation of the problem. These results hold typically in the value oracle model, where the objective function is accessible via a black box returning f(S) for a given S. We present a general approach to deriving inapproximability results in the value oracle model, based on the notion of symmetry gap. Our main result is that for any fixed instance that exhibits a certain symmetry gap in its multilinear relaxation, there is a naturally related class of instances for which a better approximation factor than the symmetry gap would require exponentially many oracle queries. This unifies several known hardness results for submodular maximization, e.g., the optimality of (1 - 1/e)-approximation for monotone submodular maximization under a cardinality constraint and the impossibility of (½ + ε)-approximation for unconstrained (nonmonotone) submodular maximization. As a new application, we consider the problem of maximizing a nonmonotone submodular function over the bases of a matroid. A (1/6 - o(1))-approximation has been developed for this problem, assuming that the matroid contains two disjoint bases. We show that the best approximation one can achieve is indeed related to packings of bases in the matroid. Specifically, for any k ≥ 2, there is a class of matroids of fractional base packing number v = k/k - 1 such that any algorithm achieving a better than (1 - 1/v) = 1/k -approximation for this class would require exponentially many value queries. In particular, there is no constant factor approximation for maximizing a nonmonotone submodular function over the bases of a general matroid. On the positive side, we present a ½(1 - 1/v - o(1))-approximation algorithm assuming fractional base packing number at least v, where v ∈ (1, 2]. We also present an improved 0.309-approximation for maximization of a nonmonotone submodular function subject to a matroid independence constraint, improving the previously known factor of ¼ - ε. For this problem, we obtain a hardness of (½ + ε)-approximation for any fixed ε > 0. [ABSTRACT FROM AUTHOR]

This paper deals with the design of efficiently computable incentive-compatible mechanisms for combinatorial optimization problems with single-minded agents each possibly having multiple private parameters. We focus on approximation algorithms for NP-hard mechanism design problems. These algorithms need to satisfy certain monotonicity properties to ensure truthfulness. Since most of the known approximation techniques do not fulfill these properties, we study alternative techniques. Our first contribution is a quite general method to transform a pseudopolynomial algorithm into a monotone fully polynomial time approximation scheme (FPTAS). This can be applied to various problems like, e.g., knapsack, constrained shortest path, or job scheduling with deadlines. For example, the monotone FPTAS for the knapsack problem gives a very efficient, truthful mechanism for single-minded multiunit auctions. The best previous result for such auctions was a 2-approximation. In addition, we present a monotone PTAS for the generalized assignment problem with any constant number of private parameters per agent. The most efficient way to solve packing integer programs (PIPs) is linear programming-based randomized rounding, which also is in general not monotone. We show that primal-dual greedy algorithms achieve almost the same approximation ratios for PIPs as randomized rounding. The advantage is that these algorithms are inherently monotone. This way, we can significantly improve the approximation ratios of truthful mechanisms for various fundamental mechanism design problems like single-minded combinatorial auctions (CAs), unsplittable flow routing, and multicast routing. Our primal-dual approximation algorithms can also be used for the winner determination in CAs with general bidders specifying their bids through an oracle. [ABSTRACT FROM AUTHOR]

We consider two- and multistage versions of stochastic combinatorial optimization problems with recourse: in this framework, the instance for the combinatorial optimization problem is drawn from a known probability distribution 7r and is only revealed to the algorithm over two (or multiple) stages. At each stage, on receiving some more information about the instance, the algorithm is allowed to build some partial solution. Since the costs of elements increase with each passing stage, there is a natural tension between waiting for later stages, to gain more information about the instance, and purchasing elements in earlier stages, to take advantages of lower costs. We provide approximation algorithms for stochastic combinatorial optimization problems (such as the Steiner tree problem, the Steiner network problem, and the vertex cover problem) by means of a simple sampling-based algorithm. In every stage, our algorithm samples the probability distribution of the requirements and constructs a partial solution to serve the resulting sample. We show that if one can construct cost-sharing functions associated with the algorithms used to construct these partial solutions, then this strategy results in provable approximation guarantees for the overall stochastic optimization problem. We also extend this approach to provide an approximation algorithm for the stochastic version of the uncapacitated facility location problem, a problem that does not fit into the simpler framework of our main model. [ABSTRACT FROM AUTHOR]

Submodular maximization generalizes many important problems including Max Cut in directed and undirected graphs and hypergraphs, certain constraint satisfaction problems, and maximum facility location problems. Unlike the problem of minimizing submodular functions, the problem of maximizing submodular functions is NP-hard. In this paper, we design the first constant-factor approximation algorithms for maximizing nonnegative (non-monotone) submodular functions. In particular, we give a deterministic local-search 1/3-approximation and a randomized 2/5-approximation algorithm for maximizing nonnegative submodular functions. We also show that a uniformly random set gives a ¼-approximation. For symmetric submodular functions, we show that a random set gives a ½-approximation, which can also be achieved by deterministic local search. These algorithms work in the value oracle model, where the submodular function is accessible through a black box returning f(S) for a given set S. We show that in this model, a (½ + ε)-approximation for symmetric submodular functions would require an exponential number of queries for any fixed ε > 0. In the model where f is given explicitly (as a sum of nonnegative submodular functions, each depending only on a constant number of elements), we prove NP-hardness of (5/6 + ε)-approximation in the symmetric case and NP-hardness of (¾ + ε)-approximation in the general case. [ABSTRACT FROM AUTHOR]

Local ratio is a well-known paradigm for designing approximation algorithms for combinatorial optimization problems. At a very high level, a local-ratio algorithm first decomposes the input weight function w into a positive linear combination of simpler weight functions or models. Guided by this process, a solution S is constructed such that S is a-approximate with respect to each model used in the decomposition. As a result, S is a-approximate under w as well. These models usually have a very simple structure that remains "unchanged" throughout the execution of the algorithm. In this work we show that adaptively choosing a model from a richer spectrum of functions can lead to a better local ratio. Indeed, by turning the search for a good model into an optimization problem of its own, we get improved approximations for a data migration problem. [ABSTRACT FROM AUTHOR]

Submodular function maximization is a central problem in combinatorial optimization, generalizing many important problems including Max Cut in directed/undirected graphs and in hypergraphs, certain constraint satisfaction problems, maximum entropy sampling, and maximum facility location problems. Unlike submodular minimization, submodular maximization is NP-hard. In this paper, we give the first constant-factor approximation algorithm for maximizing any nonnegative submodular function subject to multiple matroid or knapsack constraints. We emphasize that our results are for nonmonotone submodular functions. In particular, for any constant k, we present a ((These equations cannot be represented into ASCII text))-approximation for the submodular maximization problem under k matroid constraints, and a (1/5 - ∈)-approximation algorithm for this problem subject to k knapsack constraints (∈ > 0 is any constant). We improve the approximation guarantee of our algorithm to (These equations cannot be represented into ASCII text) for k ≥ 2 partition matroid constraints. This idea also gives a (1/k+∈)-approximation for maximizing a monotone submodular function subject to k ≥ 2 partition matroids, which is an improvement over the previously best known guarantee of 1/k+1. [ABSTRACT FROM AUTHOR]

We show that any rational convex polytope is polynomial-time representable as a 3-way line-sum transportation polytope of "slim" (r, c, 3) format. This universality theorem has important consequences for linear and integer programming and for confidential statistical data disclosure. We provide a polynomial-time embedding of arbitrary linear programs and integer programs in such slim transportation programs and in bitransportation programs. Our construction resolves several standing problems on 3-way transportation polytopes. For example, it demonstrates that, unlike the case of 2-way contingency tables, the range of values an entry can attain in any slim 3-way contingency table with specified 2-margins can contain arbitrary gaps. Our smallest such example has format (6, 4, 3). Our construction provides a powerful automatic tool for studying concrete questions about transportation polytopes and contingency tables. For example, it automatically provides new proofs for some classical results, including a well-known "real-feasible but integer-infeasible" (6, 4, 3)-transportation polytope of M. Vlach, and bitransportation programs where any feasible bitransportation must have an arbitrarily large prescribed denominator. [ABSTRACT FROM AUTHOR]

A polynomial time testable characterization of cost matrices associated with a complete digraph on n nodes such that all the Hamiltonian cycles (tours) have the same cost is well known. Tarasov [U.S.S.R. Comput. Maths. Math. Phys., 21 (1981), pp. 167-174.] obtained a characterization of cost matrices where tour costs take two distinct values. We provide a simple alternative characterization of such cost matrices, which can be tested in O(n²) time. We also provide analogous results where tours are replaced by Hamiltonian paths. When the cost matrix is skew-symmetric, we provide polynomial time testable characterizations such that the tour costs take three distinct values. Corresponding results for the case of Hamiltonian paths are also given. Using these results, special instances of the asymmetric traveling salesman problem (ATSP) are identified that are solvable in polynomial time and that have improved constant factor approximation schemes. In particular, we observe that the 3/2 performance guarantee of the Christofides algorithm extends to all metric Hamiltonian symmetric matrices. Further, we identify special classes of ATSP for which polynomial ε-approximation algorithms are available for ε ∈ {3/2, 4/3, 4r, 3r;²/2 , 4+δ/3}, where r > ½ and δ ≥ 0 are constants. [ABSTRACT FROM AUTHOR]

In the weighted rectangle stabbing problem we are given a grid in ℝ² consisting of columns and rows each having a positive integral weight, and a set of closed axis-parallel rectangles each having a positive integral demand. The rectangles are placed arbitrarily in the grid with the only assumption being that each rectangle is intersected by at least one column or row. The objective is to find a minimum-weight (multi)set of columns and rows of the grid so that for each rectangle the total multiplicity of selected columns and rows stabbing it is at least its demand. A special case of this problem, called the interval stabbing problem, arises when each rectangle is intersected by exactly one row. We describe an algorithm called STAB, which is shown to be a constant-factor approximation algorithm for different variants of this stabbing problem. [ABSTRACT FROM AUTHOR]

We discuss two approximation paradigms that were used to construct many approximation algorithms during the last two decades, the primal-dual schema and the local ratio technique. Recently, primal-dual algorithms were devised by first constructing a local ratio algorithm and then transforming it into a primal-dual algorithm. This was done in the case of the $2$-approximation algorithms for the feedback vertex set problem and in the case of the first primal-dual algorithms for maximization problems. Subsequently, the nature of the connection between the two paradigms was posed as an open question by Williamson [Math. Program., 91 (2002), pp. 447--478]. In this paper we answer this question by showing that the two paradigms are equivalent. [ABSTRACT FROM AUTHOR]

The max-bisection and min-bisection problems are to find a partition of the vertices of a graph into two equal size subsets that, respectively, maximizes or minimizes the number of edges with endpoints in both subsets. We design the first polynomial time approximation scheme for the max-bisection problem on arbitrary planar graphs solving a long-standing open problem. The method of solution involves designing exact polynomial time algorithms for computing optimal partitions of bounded treewidth graphs, in particular max- and min-bisection, which could be of independent interest. Using a similar method we design also the first polynomial time approximation scheme for max-bisection on unit disk graphs (which could also be easily extended to other geometrically defined graphs). [ABSTRACT FROM AUTHOR]

We present improved combinatorial approximation algorithms for the uncapacitated facility location problem. Two central ideas in most of our results are cost scaling and greedy improvement. We present a simple greedy local search algorithm which achieves an approximation ratio of $2.414+\epsilon$ in $\tilde{O}(n^2/\epsilon)$ time. This also yields a bicriteria approximation tradeoff of $(1+\gamma,1+2/\gamma)$ for facility cost versus service cost which is better than previously known tradeoffs and close to the best possible. Combining greedy improvement and cost scaling with a recent primal-dual algorithm for facility location due to Jain and Vazirani, we get an approximation ratio of $1.853$ in $\tilde{O}(n^3)$ time. This is very close to the approximation guarantee of the best known algorithm which is linear programming (LP)-based. Further, combined with the best known LP-based algorithm for facility location, we get a very slight improvement in the approximation factor for facility location, achieving $1.728$. We also consider a variant of the capacitated facility location problem and present improved approximation algorithms for this. [ABSTRACT FROM AUTHOR]

Local search algorithms for combinatorial optimization problems are generally of pseudopolynomial running time, and polynomial-time algorithms are not often known for finding locally optimal solutions for NP-hard optimization problems. We introduce the concept of ε-local optimality and show that, for every ε > 0, an ε-local optimum can be identified in time polynomial in the problem size and 1/ε whenever the corresponding neighborhood can be searched in polynomial time. If the neighborhood can be searched in polynomial time for a ε-local optimum, a variation of our main algorithm produces a (δ+ ε)-local optimum in time polynomial in the problem size and 1/ε. As a consequence, a combinatorial optimization problem has a fully polynomial-time approximation scheme if and only if the problem of determining a better neighbor in an exact neighborhood has a fully polynomial-time approximation scheme. [ABSTRACT FROM AUTHOR]

We present an 8-approximation algorithm for the problem of finding a minimum weight subset feedback vertex set (or subset-fvs, in short). The input in this problem consists of an undirected graph G = (V, E) with vertex weights c(v) and a subset of vertices S called special vertices. A cycle is called interesting if it contains at least one special vertex. A subset of vertices is called a subset-fvs with respect to S if it intersects every interesting cycle. The goal is to find a minimum weight subset-fvs. The best previous algorithm for the general case provided only a logarithmic approximation factor. The minimum weight subset-fvs problem generalizes two NP-complete problems: the minimum weight feedback vertex set problem in undirected graphs and the minimum weight multiway vertex cut problem. The main tool that we use in our algorithm and its analysis is a new version of multicommodity flow, which we call relaxed multicommodity flow. Relaxed multicommodity flow is a hybrid of multicommodity flow and multiterminal flow. [ABSTRACT FROM AUTHOR]

In heterogeneous networks, sending messages may incur different delays on different links, and each node may have a different switching time between messages. The well-studied telephone model is obtained when all link delays and switching times are equal to one unit. We investigate the problem of finding the minimum time required to multicast a message from one source to a subset of the nodes of size k. The problem is NP-hard even in the basic telephone model. We present a polynomial-time algorithm that approximates the minimum multicast time within a factor of O(log k). Our algorithm improves on the best known approximation factor for the telephone log n model by a factor of O(log n&frac;log log k). No approximation algorithms were known for the general model considered in this paper. [ABSTRACT FROM AUTHOR]

We present a linear programming-based method for finding "gadgets," i.e., combinatorial structures reducing constraints of one optimization problem to constraints of another. A key step in this method is a simple observation which limits the search space to a finite one. Using this new method we present a number of new, computer-constructed gadgets for several different reductions. This method also answers a question posed by Bellare, Goldreich, and Sudan [SIAM J. Comput., 27 (1998), pp. 804-915] of how to prove the optimality of gadgets: linear programming duality gives such proofs. The new gadgets, when combined with recent results of Håstad [Proceedings of the 29th ACM Symposium on Theory of Computing, 1997, pp. 1-10], improve the known inapproximability results for MAX CUT and MAX DICUT, showing that approximating these problems to within factors of 16/17+ ∊ and 12/13+ ∊ , respectively, is NP-hard for every ∊ > 0. Prior to this work, the best-known inapproximability thresholds for both problems were 71/72 (M. Bellare, O. Goldreich, and M. Sudan [SIAM J. Comput., 27 (1998), pp. 804-915]). Without using the gadgets from this paper, the best possible hardness that would follow from Bellare, Goldreich, and Sudan and Håstad is 18/19. We also use the gadgets to obtain an improved approximation algorithm for MAX3 SAT which guarantees an approximation ratio of .801. [ABSTRACT FROM AUTHOR]

Several important NP-hard combinatorial optimization problems can be posed as packing/covering integer programs; the randomized rounding technique of Raghavan and Thompson is a powerful tool with which to approximate them well. We present one elementary unifying property of all these integer linear programs and use the FKG correlation inequality to derive an improved analysis of randomized rounding on them. This yields a pessimistic estimator, thus presenting deterministic polynomial-time algorithms for them with approximation guarantees that are significantly better than those known. [ABSTRACT FROM AUTHOR]