Search

We achieve a (randomized) polynomial-time approximation scheme (PTAS) for the Steiner forest problem in doubling metrics. Before our work, a PTAS was given only for the Euclidean plane in [G. Borradaile, P. N. Klein, and C. Mathieu, in FOCS, IEEE Computer Society, 2008, pp. 115--124]. Our PTAS also shares similarities with the dynamic programming for sparse instances used in [Y. Bartal, L. Gottlieb, and R. Krauthgamer, in STOC, ACM, 2012, pp. 663--672] and [T-H. H. Chan and S.-H. Jiang, in SODA, SIAM, 2016, pp. 754--765]. However, extending previous approaches requires overcoming several nontrivial hurdles, and we make the following technical contributions. (1) We prove a technical lemma showing that Steiner points have to be ''near"" the terminals in an optimal Steiner tree. This enables us to define a heuristic to estimate the local behavior of the optimal solution, even though the Steiner points are unknown in advance. This lemma also generalizes previous results in the Euclidean plane and may be of independent interest for related problems involving Steiner points. (2) We develop a novel algorithmic technique known as ''adaptive cells"" to overcome the difficulty of keeping track of multiple components in a solution. Our idea is based on but significantly different from the previously proposed ''uniform cells"" in [G. Borradaile, P. N. Klein, and C. Mathieu, in FOCS, IEEE Computer Society, 2008, pp. 115--124], where techniques cannot be readily applied to doubling metrics. [ABSTRACT FROM AUTHOR]

We present the first online algorithms for the nonuniform, multicommodity buy-atbulk (MC-BB) network design problem. Our competitive ratios qualitatively match the best known approximation factors for the corresponding offline problems. In particular, we show (a) a polynomial time online algorithm with a polylogarithmic competitive ratio for the MC-BB problem in undirected edge-weighted graphs, (b) a quasi-polynomial time online algorithm with a polylogarithmic competitive ratio for the MC-BB problem in undirected node-weighted graphs, (c) for any fixed ε > 0, a polynomial time online algorithm with a competitive ratio of Õ(k1/2+ε) (where k is the number ofdemands, and the tilde hides polylog factors) for MC-BB in directed graphs, and (d) algorithmswith matching competitive ratios for the prize-collecting variant of all the preceding problems. Priorto our work, a logarithmic competitive ratio was known for undirected, edge-weighted graphs onlyfor the special case of uniform costs [B. Awerbuch and Y. Azar, FOCS, 1997, pp. 542{547], anda polylogarithmic-competitive algorithm was known for the edge-weighted single-sink problem [A.Meyerson, Procedings of SPAA, 2004, pp. 275{280]. We believe no online algorithm was known in thenode-weighted and directed settings, even for uniform costs. Our main technical contribution is anonline reduction theorem of MC-BB problems to their single-sink counterparts. We use the conceptof junction-tree solutions from [C. Chekuri, M. T. Hajiaghayi, G. Kortsarz, and M. R. Salavatipour, Proceedings of FOCS, 2006, pp. 677{686], which play an important role in solving the offline versionsof the problem via a greedy subroutine-an inherently offline procedure. We use just the existence of good junction-trees for our reduction. [ABSTRACT FROM AUTHOR]

Moss and Rabani study constrained node-weighted Steiner tree problems with two independent weight values associated with each node, namely, cost and prize (or penalty). They give an O(log n)-approximation algorithm for the node-weighted prize-collecting Steiner tree problem (PCST) where the goal is to minimize the cost of a tree plus the penalty of vertices not covered by the tree. They use the algorithm for PCST to obtain a bicriteria (2;O(log n))-approximation algorithm for the budgeted node-weighted Steiner tree problem where the goal is to maximize the prize of a tree with a given budget for its cost. Their solution may cost up to twice the budget, but collects a factor ( 1 log n ) of the optimal prize. We improve these results from at least two aspects. Our rst main result is a primal-dual O(log h)-approximation algorithm for a more general problem, node-weighted prize-collecting Steiner forest (PCSF), where we have h demands each requesting the connectivity of a pair of vertices. Our algorithm can be seen as a greedy algorithm which reduces the number of demands by choosing a structure with minimum cost-to-reduction ratio. This natural style of argument leads to a much simpler algorithm than that of Moss and Rabani for PCST. Our second main contribution is for the budgeted node-weighted Steiner tree problem, which is also an improvement to the work of Moss and Rabani. In the unrooted case, we improve upon an existing O(log2 n)-approximation by Guha et al., and present an O(log n)-approximation algorithm without any budget violation. For the rooted case, where a speci ed vertex has to appear in the solution tree, we improve the bicriteria result of Moss and Rabani to the bicriteria approximation ratio of (1 + ;O(log n)=2) for any positive (possibly subconstant) ∈. That is, for any permissible budget violation 1 + ∈, we present an algorithm achieving a trade o in the guarantee for the prize. Indeed, we show that this is almost tight for the natural linear-programming relaxation used by us as well as in the previous works. [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 present improved approximation algorithms in stochastic optimization. We prove that the multistage stochastic versions of covering integer programs (such as set cover and vertex cover) admit essentially the same approximation algorithms as their standard (nonstochastic) coun- terparts; this improves upon work of Swamy and Shmoys which shows an approximability that de- pends multiplicatively on the number of stages. We also present approximation algorithms for facility location and some of its variants in the 2-stage recourse model, improving on previous approximation guarantees. We give a 2:2975-approximation algorithm in the standard polynomial-scenario model and an algorithm with an expected per-scenario 2:4957-approximation guarantee, which is applicable to the more general black-box distribution model. [ABSTRACT FROM AUTHOR]

We consider the following geometric optimization problem: find a convex polygon of maximum area contained in a given simple polygon P with n vertices. We give a randomized near- linear-time (1 - ε)-approximation algorithm for this problem: in O(n(log² n + (1/ε³) log n + 1=ε4) time we find a convex polygon contained in P that, with probability at least 2=3, has area at least (1 - ε) times the area of an optimal solution. We also obtain similar results for the variant of computing a convex polygon inside P with maximum perimeter. To achieve these results we provide new results in geometric probability. The first result is a bound relating the area of the largest convex body inside P to the probability that two points chosen uniformly at random inside P are mutually visible. The second result is a bound on the expected value of the difference between the perimeter of any planar convex body K and the perimeter of the convex hull of a uniform random sample inside K. [ABSTRACT FROM AUTHOR]

The FitzHugh{Nagumo (FHN) system of PDEs is a generic model for excitable media, often used to build a qualitative understanding of electrophysiological phenomena. A well-characterized traveling pulse solution to FHN serves as a model for action potentials in cardiac tissue and other contexts. The stability of the traveling pulse has been well studied, but the more global problem of predicting when an arbitrary initial condition will converge to the uniform rest solution and when it will converge to the traveling pulse remains unsolved. Here we prove the existence of an invariant winding number in an asymptotic limit of the FHN system called the singular FHN system (SFHN) that provides a crucial step toward a global convergence result. This result is valid for a relatively general class of nonlinearities. In addition, we provide evidence that our SFHN results extend with limitations to FHN and outline conditions under which the SFHN approximation fails. The invariant winding number provides explanations for several observations of physiological relevance. For example, it explains the requirements on stimulus protocols that allow the formation and elimination of reentrant rhythms in cardiac tissue. [ABSTRACT FROM AUTHOR]

We revisit a classical problem in transportation, known as the (bilevel) continuous network design problem, CNDP for short. Given a graph for which the latency of each edge depends on the ratio of the edge flow and the capacity installed, the goal is to find an optimal investment in edge capacities so as to minimize the sum of the routing costs of the induced Wardrop equilibrium and the investment costs for installing the edge's capacities. While this problem is considered to be challenging in the literature, its complexity status was still unknown. We close this gap, showing that CNDP is strongly NP-hard and APX-hard, both on directed and undirected networks and even for instances with affine latencies. As for the approximation of the problem, we first provide a detailed analysis for a heuristic studied by Marcotte for the special case of monomial latency functions [P. Marcotte, Math. Prog., 34 (1986), pp. 142{162]. We derive a closed form expression of its approximation guarantee for arbitrary sets of latency functions. We then propose a different approximation algorithm and show that it has the same approximation guarantee. Then, we prove that using the better of the two approximation algorithms results in a strictly improved approximation guarantee for which we derive a closed form expression. For affine latencies, for example, this best-of-two approach achieves an approximation factor of 49=41 ≈ 1:195, which improves on the factor of 5=4 that has been shown before by Marcotte. [ABSTRACT FROM AUTHOR]

Sensor networks are ubiquitously used for detection and tracking and, as a result, covering is one of the main tasks of such networks. We study the problem of maximizing the coverage lifetime of a barrier by mobile sensors with limited battery power, where the coverage lifetime is the time until there is a breakdown in coverage due to the death of a sensor. Sensors are first deployed and then coverage commences. Energy is consumed in proportion to the distance traveled for mobility, while for coverage, energy is consumed in direct proportion to the radius of the sensor raised to a constant exponent. We study two variants which are distinguished by whether the sensing radii are given as part of the input or can be optimized: the fixed radii problem and the variable radii problem. We design parametric search algorithms for both problems for the case where the final order of the sensors is predetermined (e.g., sensors cannot swap locations and the initial order must be preserved) and for the case where sensors are initially located at barrier endpoints. In contrast, we show that the variable radii problem is strongly NP-hard and provide hardness of approximation results for fixed radii for the case where all the sensors are initially colocated at an internal point of the barrier. [ABSTRACT FROM AUTHOR]

This paper compares the performance of penalty and Lagrange multiplier approaches for the necessary unit-length constraint in the computation of liquid crystal equilibrium configurations. Building on previous work in [SIAM J. Sci. Comput., 37 (2015), pp. S157-S176; SIAM J. Numer. Anal., 53 (2015), pp. 2226-2254], the penalty method is derived and well-posedness of the linearizations within the nonlinear iteration is discussed. In addition, the paper considers the effects of tailored trust-region methods in the context of finite-element discretizations and nested iteration for both formulations. Such methods are aimed at increasing the efficiency and robustness of each algorithm's nonlinear iterations. Three representative elastic equilibrium problems are considered to examine each method's performance. The first two configurations have analytical expressions for their exact solutions and, therefore, convergence to the true solution is considered. The third problem considers complicated boundary conditions, relevant in ongoing research, simulating surface nano-patterning. Finally, a novel multigrid scheme is introduced and tested for electrically and flexoelectrically coupled models to establish scalability for highly complicated applications. The Lagrange multiplier method is found to outperform the penalty method in a number of measures, the developed trust regions are shown to improve robustness, and nested iteration proves highly effective at reducing computational costs. [ABSTRACT FROM AUTHOR]

We consider the Unconstrained Submodular Maximization problem in which we are given a nonnegative submodular function f : 2N → ℝ+, and the objective is to find a subset S ⊆ N maximizing f(S). This is one of the most basic submodular optimization problems, having a wide range of applications. Some well-known problems captured by Unconstrained Submodular Maximization include Max-Cut, Max-DiCut, and variants of Max-SAT and maximum facility location. We present a simple randomized linear time algorithm achieving a tight approximation guarantee of 1/2, thus matching the known hardness result of Feige, Mirrokni, and Vondrák [SIAM J. Comput., 40 (2011), pp. 1133-1153]. Our algorithm is based on an adaptation of the greedy approach which exploits certain symmetry properties of the problem. [ABSTRACT FROM AUTHOR]

We give a lower bound on the iteration complexity of a natural class of Lagrangianrelaxation algorithms for approximately solving packing/covering linear programs. We show that, given an input with m random 0/1-constraints on n variables, with high probability, any such algorithm requires Ω(ρ log(m)/ϵ2) iterations to compute a (1 + ϵ)-approximate solution, where ρ is the width of the input. The bound is tight for a range of the parameters (m, n, ρ, ϵ). The algorithms in the class include Dantzig-Wolfe decomposition, Benders' decomposition, Lagrangian relaxation as developed by Held and Karp for lower-bounding TSP, and many others (e.g., those by Plotkin, Shmoys, and Tardos and Grigoriadis and Khachiyan). To prove the bound, we use a discrepancy argument to show an analogous lower bound on the support size of (1 + ϵ)-approximate mixed strategies for random two-player zero-sum 0/1-matrix games. [ABSTRACT FROM AUTHOR]

Trevisan [SIAM J. Comput., 41 (2012), pp. 1769-1786] presented an algorithm for Max-Cut based on spectral partitioning techniques. This is the first algorithm for Max-Cut with an approximation guarantee strictly larger than 1/2 that is not based on semidefinite programming. Trevisan showed that its approximation ratio is of at least 0.531. In this paper we improve this bound up to 0.614247. We also define and extend this result for the more general maximum colored cut problem. [ABSTRACT FROM AUTHOR]

Many scientific and engineering applications feature nonsmooth convex minimization problems over convex sets. In this paper, we address an important instance of this broad class where we assume that the nonsmooth objective is equipped with a tractable proximity operator and that the convex constraint set affords a self-concordant barrier. We provide a new joint treatment of proximal and self-concordant barrier concepts and illustrate that such problems can be efficiently solved, without the need of lifting the problem dimensions, as in disciplined convex optimization approach. We propose an inexact path-following algorithmic framework and theoretically characterize the worst-case analytical complexity of this framework when the proximal subproblems are solved inexactly. To show the merits of our framework, we apply its instances to both synthetic and real-world applications, where it shows advantages over standard interior point methods. As a byproduct, we describe how our framework can obtain points on the Pareto frontier of regularized problems with self-concordant objectives in a tuning free fashion. [ABSTRACT FROM AUTHOR]

Let G = (V, E) be a simple graph of maximum degree Δ. The edges of G can be colored with at most Δ + 1 colors by Vizing's theorem. We study lower bounds on the size of subgraphs of G that can be colored with A colors. Vizing's theorem gives a bound of Δ/Δ + 1 |E|. This is known to be tight for cliques κΔ + 1 when Δ is even. However, for Δ = 3 it was improved to 26/31 |E| by Albertson and Haas [Discrete Math., 148 (1996), pp. 1-7] and later to 6/7|E| by Rizzi [Discrete Math., 309 (2009), pp. 4166-4170]. It is tight for B3, the graph isomorphic to a K4 with one edge subdivided. We improve previously known bounds for Δ ∈ {3,..., 7}, under the assumption that for Δ = 3,4,6, graph G is not isomorphic to B3, K5, and K7, respectively. For Δ ≥ 4 these are the first results which improve over the Vizing's bound. We also show a new bound for subcubic multigraphs not isomorphic to K3 with one edge doubled. In the second part, we give approximation algorithms for the maximum κ-edge-colorable subgraph problem, where given a graph G (without any bound on its maximum degree or other restrictions) one has to find a κ-edge-colorable subgraph with the maximum number of edges. In particular, when G is simple for κ = 3, 4, 5, 6, 7 we obtain approximation ratios of 13/15, 9/11, 19/22, 23/27, and 22/25, respectively. We also present a 7/9-approximation for κ = 3 when G is a multigraph. The approximation algorithms follow from a new general framework that can be used for any value of κ. [ABSTRACT FROM AUTHOR]

In a classic optimization problem, the complete input data is assumed to be known to the algorithm. This assumption may not be true anymore in optimization problems motivated by the Internet where part of the input data is private knowledge of independent selfish agents. The goal of algorithmic mechanism design is to provide (in polynomial time) a solution to the optimization problem and a set of incentives for the agents such that disclosing the input data is a dominant strategy for the agents. In the case of NP-hard problems, the solution computed should also be a good approximation of the optimum. In this paper we focus on mechanism design for multiobjective optimization problems. In this setting we are given a main objective function and a set of secondary objectives which are modeled via budget constraints. Multiobjective optimization is a natural setting for mechanism design as many economical choices ask for a compromise between different, partially conflicting goals. The main contribution of this paper is showing that two of the main tools for the design of approximation algorithms for multiobjective optimization problems, namely, approximate Pareto sets and Lagrangian relaxation, can lead to truthful approximation schemes. By exploiting the method of approximate Pareto sets, we devise truthful deterministic and randomized multicriteria fully polynomial-time approximation schemes (FPTASs) for multiobjective optimization problems whose exact version admits a pseudopolynomial-time algorithm, as, for instance, the multibudgeted versions of minimum spanning tree, shortest path, maximum (perfect) matching,and matroid intersection. Our construction also applies to multidimensional knapsack and multiunit combinatorial auctions. Our FPTASs compute a (1+ε)-approximate solution violating each budget constraint by a factor (1+ ε). When feasible solutions induce an independence system, i.e., when subsets of feasible solutions are feasible as well, we present a PTAS (not violating any constraint), which combines the approach above with a novel monotone way to guess the heaviest elements in the optimum solution. Finally, we present a universally truthful Las Vegas PTAS for minimum spanning tree with a single budget constraint, where one wants to compute a minimum cost spanning tree whose length is at most a given value L. This result is based on the Lagrangian relaxation method, in combination with our monotone guessing step and with a random perturbation step (ensuring low expected running time). This result can be derandomized in the case of integral lengths. All the mentioned results match the best known approximation ratios, which are, however, obtained by nontruthful algorithms. [ABSTRACT FROM AUTHOR]

Minimum-weight triangulation (MWT) is NP-hard. It has a polynomial-time constant-factor approximation algorithm, and a variety of effective polynomial-time heuristics that, for many instances, can find the exact MWT. Linear programs (LPs) for MWT are well-studied, but previously no connection was known between any LP and any approximation algorithm or heuristic for MWT. Here we show the first such connections: For an LP formulation due to Dantzig, Hoffman, and Hu [Math. Programming, 31 (1985), pp. 1-14], (i) the integrality gap is constant, and (ii) given any instance, if the aforementioned heuristics find the MWT, then so does the LP. [ABSTRACT FROM AUTHOR]

We give the first black-box reduction from approximation algorithms to truthful approximation mechanisms for a non-trivial class of multi-parameter problems. Specifically, we prove that every welfare-maximization problem that admits a fully polynomial-time approximation scheme (FPTAS) and can be encoded as a packing problem also admits a truthful-in-expectation randomized mechanism that is an FPTAS. Our reduction makes novel use of smoothed analysis by employing small perturbations as a tool in algorithmic mechanism design. We develop a "duality" between linear perturbations of the objective function of an optimization problem and of its feasible set, and we use the "primal" and "dual" viewpoints to prove the running time bound and the truthfulness guarantee, respectively, for our mechanism. [ABSTRACT FROM AUTHOR]

We consider the general polynomial optimization problem P : /* = min{f(x) : x ∈ K}, where K is a compact basic semialgebraic set. We first show that the standard Lagrangian relaxation yields a lower bound as close as desired to the global optimum /*, provided that it is applied to a problem P equivalent to P, in which sufficiently many redundant constraints (products of the initial ones) are added to the initial description of P. Next we show that the standard hierarchy of linear program (LP-)relaxations of P (in the spirit of the Sherali--Adams reformulation-linearization technique) can be interpreted as a brute force simplification of the above Lagrangian relaxation in which a nonnegative polynomial (with coefficients to be determined) is replaced with a constant polynomial equal to zero. Inspired by this interpretation, we provide a systematic improvement of the LP-hierarchy by doing a much less brutal simplification which results into a parametrized hierarchy of semidefinite programs (and not LPs any more). For each semidefinite program in the parametrized hierarchy, the semidefinite constraint has a fixed size O(nk), independent of the rank in the hierarchy. When applied to a nontrivial class of convex problems, the first relaxation of the parametrized hierarchy is exact, in contrast with the LP-hierarchy, where convergence cannot be finite. [ABSTRACT FROM AUTHOR]

Given a universe U of n elements and a weighted collection S of m subsets of U, the universal set cover problem is to a priori map each element u ∈ U to a set S(u) ∈ S containing u such that any set X ⊆ U is covered by S(X) = ∪u∈XS(u). The aim is to find a mapping such that the cost of S(X) is as close as possible to the optimal set cover cost for X. (Such problems are also called oblivious or a priori optimization problems.) Unfortunately, for every universal mapping, the cost of S(X) can be Ω(√n) times larger than optimal if the set X is adversarially chosen. In this paper we study the performance on average, when X is a set of randomly chosen elements from the universe: we show how to efficiently find a universal map whose expected cost is O(logmn) times the expected optimal cost. In fact, we give a slightly improved analysis and show that this is the best possible. We generalize these ideas to weighted set cover and show similar guarantees to (nonmetric) facility location, where we have to balance the facility opening cost with the cost of connecting clients to the facilities. We show applications of our results to universal multicut and disc-covering problems and show how all these universal mappings give us algorithms for the stochastic online variants of the problems with the same competitive factors. [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]

In this paper, we extend the notion of person-by-person (pbp) optimization to binary decision spaces. The novelty of our approach is the adaptation to a dynamic team context of notions borrowed from the pseudo-boolean optimization field as completely local-global or unimodal functions and submodularity. We also generalize the concept of pbp optimization to the case where groups of m decisions makers make joint decisions sequentially, which we refer to as mbm optimization. The main contribution is a description of sufficient conditions, verifiable in polynomial time, under which a pbp or an mbm optimization algorithm converges to the team-optimum. As a second contribution, we present a local and greedy algorithm characterized by approximate decision strategies (i.e., strategies based on a local state vector) that return the same decisions as in the complete information framework (where strategies are based on full state vector). As a last contribution, we also show that there exists a subclass of submodular team problems, recognizable in polynomial time, for which the pbp optimization converges for at least an opportune initialization of the algorithm. [ABSTRACT FROM AUTHOR]

We present an O(log² k)-approximation algorithm for the problem of finding a k-vertex connected spanning subgraph of minimum cost, where n is the number of vertices in an input graph, and k is a connectivity requirement. Our algorithm is the first that achieves a polylog-arithmic approximation ratio for all values of k and n, and it works for both directed and undirected graphs. As in previous works, we use the Frank-Tardos algorithm for finding k-outconnected subgraphs as a subroutine. However, with our structural lemmas, we are able to show that we need only partial solutions returned by the Frank-Tardos algorithm; thus, we can avoid paying the whole cost of an optimal solution every time the algorithm is applied. [ABSTRACT FROM AUTHOR]

One of the classic results in scheduling theory is the 2-approximation algorithm by Lenstra, Shmoys, and Tardos for the problem of scheduling jobs to minimize makespan on unrelated machines; i.e., job j requires time pij if processed on machine i. More than two decades after its introduction it is still the algorithm of choice even in the restricted model where processing times are of the form pij ∈ {pj∞}. This problem, also known as the restricted assignment problem, is NP-hard to approximate within a factor less than 1.5, which is also the best known lower bound for the general version. Our main result is a polynomial time algorithm that estimates the optimal makespan of the restricted assignment problem within a factor 33/17 + Ε ≈ 1.9412 + Ε, where Ε > 0 is an arbitrarily small constant. The result is obtained by upper bounding the integrality gap of a certain strong linear program, known as the configuration LP, that was previously successfully used for the related Santa Claus problem. Similar to the strongest analysis for that problem our proof is based on a local search algorithm that will eventually find a schedule of the mentioned approximation guarantee but is not known to converge in polynomial time. [ABSTRACT FROM AUTHOR]

Stochastic optimization problems provide a means to model uncertainty in the input data where the uncertainty is modeled by a probability distribution over the possible realizations of the actual data. We consider a broad class of these problems in which the realized input is revealed through a series of stages and hence are called multistage stochastic programming problems. Multi stage stochastic programming and, in particular, multi stage stochastic linear programs with full recourse, is a domain that has received a great deal of attention within the operations research community, mostly from the perspective of computational results in application settings. Our main result is to give the first fully polynomial approximation scheme for a broad class of multistage stochastic linear programming problems with any constant number of stages. The algorithm analyzed, known as the sample average approximation method, is quite simple and is the one most commonly used in practice. The algorithm accesses the input by means of a "black box" that can generate, given a series of outcomes for the initial stages, a sample of the input according to the conditional probability distribution (given those outcomes). We use this to obtain the first approximation algorithms for a variety of k-stage generalizations of basic combinatorial optimization problems including the set cover, vertex cover, multicut on trees, facility location, and multicommodity flow problems. [ABSTRACT FROM AUTHOR]

A seminal result of Reed et al. [Combinatorica, 16 (1996), pp. 535-554] says that a directed graph has either k vertex-disjoint directed circuits or a set of at most f(k) vertices meeting all directed circuits. This paper aims at generalizing their result to packing directed circuits through a prescribed set S of vertices. Such a circuit is called an S-circuit. Even et al. [Algorithmica, 20 (1998), pp. 151-174] showed a fractional version of packing S-circuits. In this paper, we show that the fractionality can be bounded by at most one-fifth: Given an integer k and a vertex subset S, whose size may not depend on k, we prove that either G has a 1/5-integral packing of k disjoint S-circuits, i.e., each vertex appears in at most five of these S-circuits, or G has a vertex set X of order at most f(k) (for some function f of k) such that G - X has no such circuit. We also give a fixed-parameter tractable approximation algorithm for finding a 1/5-integral packing of S-circuits. This algorithm finds a 1/5-integral packing of size approximately k in polynomial time if it has a 1/5-integral packing of size k for a given directed graph and an integer k. [ABSTRACT FROM AUTHOR]

We present a bundle method for convex nondifferentiable minimization where the model is a piecewise-quadratic convex approximation of the objective function. Unlike standard bundle approaches, the model only needs to support the objective function from below at a properly chosen (small) subset of points, as opposed to everywhere. We provide the convergence analysis for the algorithm, with a general form of master problem which combines features of trust region stabilization and proximity stabilization, taking care of all the important practical aspects such as proper handling of the proximity parameters and the bundle of information. Numerical results are also reported. [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 study the maximum weight matching problem in the semi-streaming model, and improve on the currently best one-pass algorithm due to Zelke [Proceedings of the 25th Annual Symposium on Theoretical Aspects of Computer Science, 2008, pp. 669-680] by devising a deterministic approach whose performance guarantee is 4.91 + ε. In addition, we study preemptive online algorithms, a class of algorithms related to one-pass semi-streaming algorithms, where we are allowed to maintain only a feasible matching in memory at any point in time. We provide a lower bound of 4.967 on the competitive ratio of any such deterministic algorithm, and hence show that future improvements will have to store in memory a set of edges that is not necessarily a feasible matching. We conclude by presenting an empirical study, conducted in order to compare the practical performance of our approach to that of previously suggested algorithms. [ABSTRACT FROM AUTHOR]

The reduced basis method was introduced for the accurate online evaluation of solutions to a parameter dependent family of elliptic PDEs. Abstractly, it can be viewed as determining a "good" n-dimensional space Hn to be used in approximating the elements of a compact set. F in a Hilbert space H. One by now popular computational approach is to find Hn through a greedy strategy. It is natural to compare the approximation performance of the Hn generated by this strategy with that of the Kolmogorov widths dn(F) since the latter gives the smallest error that can be achieved by subspaces of fixed dimension n. The first such comparisons, given in [A. Buffa et al., ESAIM Math. Model. Numer. Anal., 2011, to appear], show that the approximation error, σn(F) := dist(F, Hn), obtained by the greedy strategy satisfies σn(F) ≤ Cn2ndn(F). In this paper, various improvements of this result will be given. Among these, it is shown that whenever dn(F) ≤ Mn-α for all n > 0 and some M,α > 0, we also have σn(F) ≤ Cn2ndn for all n > 0, where Cα depends only on α. Similar results are derived for generalized exponential rates of the form Me-αn. The exact greedy algorithm is not always computationally feasible, and a commonly used computationally friendly variant can be formulated as a "weak greedy algorithm." The results of this paper are established for this version as well. [ABSTRACT FROM AUTHOR]

We study the PRIZE-COLLECTING STEINER TREE (PCST), PRIZE-COLLECTING TRAVELING SALESMAN (PCTSP), and PRIZE-COLLECTING PATH (PC-PATE) problems. Given a graph (V, E) with a cost on each edge and a penalty (a.k.a. prize) on each node, the goal is to find a tree (for PCST), cycle (for PCTSP), or path (for PC-PATH) that minimizes the sum of the edge costs in the tree/cycle/path and the penalties of the nodes not spanned by it. In addition to being a useful theoretical tool for helping to solve other optimization problems, PCST has been applied fruitfully by AT&T to the optimization of real-world telecommunications networks. The most recent improvements for the first two problems, a 2-approximation algorithm for each, appeared first in 1992; a 2-approximation for PC-PATH appeared in 2003. The natural linear programming relaxation of POST has an integrality gap of 2, which has been a barrier to further improvements for this problem. We present (2- e)-approximation algorithms for all three problems, connected by a unified technique for improving prize-collecting algorithms that allows us to circumvent the integrality gap barrier. Specifically, our approximation ratio for PRIZE-COLLECTING STEINER TREE is below 1.9672. [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]

We present a data structure for answering approximate shortest path queries in a planar subdivision from a fixed source. Let ρ? ⩾ 1 be a real number. Distances in each face of this subdivision are measured by a possibly asymmetric convex distance function whose unit disk is contained in a concentric unit Euclidean disk and contains a concentric Euclidean disk with radius 1/ρ?. Different convex distance functions may be used for different faces, and obstacles are allowed. Let ϵ be any number strictly between 0 and 1. Our data structure returns a (1+ϵ) approximation of the shortest path cost from the fixed source to a query destination in O(log ρn/ϵ ) time. Afterwards, a (1 +ϵ)-approximate shortest path can be reported in O(log n) time plus the complexity of the path. The data structure uses O(ρ2n3ϵ2 log ρn/ϵ ) space and can be built in O( ρ2n3/ϵ2 (log ρρn/ ϵ )2) time. Our time and space bounds do not depend on any other parameter; in particular, they do not depend on any geometric parameter of the subdivision such as the minimum angle. [ABSTRACT FROM AUTHOR]

We present algorithmic and hardness results for network design problems with degree or order constraints. The first problem we consider is the SURVIVABLE NETWORK DESIGN problem with degree constraints on vertices. The objective is to find a minimum cost subgraph which satisfies connectivity requirements between vertices and also degree upper bounds Bv on the vertices. This includes the well-studied MINIMUM BOUNDED DEGREE SPANNING TREE problem as a special case. Our main result is a (2, 2Bv+3)-approximation algorithm for the edge-connectivity SURVIVABLE NETWORK DESIGN problem with degree constraints, where the cost of the returned solution is at most twice the cost of an optimum solution (satisfying the degree bounds) and the degree of each vertex v is at most 2Bv +3. This implies the first constant factor (bicriteria) approximation algorithms for many degree constrained network design problems, including the MINIMUM BOUNDED DEGREE STEINER FOREST problem. Our results also extend to directed graphs and provide the first constant factor (bicriteria) approximation algorithms for the MINIMUM BOUNDED DEGREE ARBORESCENCE problem and the Minimum Bounded Degree Strongly κ-Edge-Connected Subgraph problem. In contrast, we show that the vertex-connectivity SURVIVABLE NETWORK DESIGN problem with degree constraints is hard to approximate, even when the cost of every edge is zero. A striking aspect of our algorithmic result is its simplicity. It is based on the iterative relaxation method, which is an extension of Jain's iterative rounding method. This provides an elegant and unifying algorithmic framework for a broad range of network design problems. We also study the problem of finding a minimum cost λ-edge-connected subgraph with at least κ vertices, which we call the (κ, λ)-subgraph problem. This generalizes some well-studied classical problems such as the κ-MST and the minimum cost λ-edge-connected subgraph problems. We give a polylogarithmic approximation for the (κ, 2)-subgraph problem. However, by relating it to the Densest κ-Subgraph problem, we provide evidence that the (κ, λ)-subgraph problem might be hard to approximate for arbitrary λ. [ABSTRACT FROM AUTHOR]

In an online linear optimization problem, on each period t, an online algorithm chooses st ϵ S from a fixed (possibly infinite) set S of feasible decisions. Nature (who may be adversarial) chooses a weight vector wt ϵ ℝn, and the algorithm incurs cost c(st, wt), where c is a fixed cost function that is linear in the weight vector. In the full-information setting, the vector wt is then revealed to the algorithm, and in the bandit setting, only the cost experienced, c(st, wt), is revealed. The goal of the online algorithm is to perform nearly as well as the best fixed s ϵ S in hindsight. Many repeated decision-making problems with weights fit naturally into this framework, such as online shortest-path, online traveling salesman problem (TSP), online clustering, and online weighted set cover. Previously, it was shown how to convert any efficient exact offline optimization algorithm for such a problem into an efficient online algorithm in both the full-information and the bandit settings, with average cost nearly as good as that of the best fixed s ϵ S in hindsight. However, in the case where the offline algorithm is an approximation algorithm with ratio α > 1, the previous approach worked only for special types of approximation algorithms. We show how to convert any offline approximation algorithm for a linear optimization problem into a corresponding online approximation algorithm, with a polynomial blowup in runtime. If the offline algorithm has an α-approximation guarantee, then the expected cost of the online algorithm on any sequence is not much larger than a times that of the best s ϵ S, where the best is chosen with the benefit of hindsight. Our main innovation is combining Zinkevich's algorithm for convex optimization with a geometric transformation that can be applied to any approximation algorithm. Standard techniques generalize the above result to the bandit setting, except that a "barycentric spanner" for the problem is also (provably) necessary as input. Our algorithm can also be viewed as a method for playing large repeated games, where one can compute only approximate best responses, rather than best responses. [ABSTRACT FROM AUTHOR]

We study graph properties that are testable for bounded-degree graphs in time independent of the input size. Our goal is to distinguish between graphs having a predetermined graph property and graphs that are far from every graph having that property. It is well known that in the bounded-degree graph model (where two graphs are considered "far" if they differ in ϵn edges for a positive constant ϵ), many graph properties cannot be tested even with a constant or even with a polylogarithmic number of queries. Therefore in this paper we focus our attention on testing graph properties for special classes of graphs. Specifically, we show that every hereditary graph property is testable with a constant number of queries provided that every sufficiently large induced subgraph of the input graph has poor expansion. This result implies that, for example, any hereditary property (e.g., k-colorability, H-freeness, etc.) is testable in the bounded-degree graph model for planar graphs, graphs with bounded genus, interval graphs, etc. No such results have been known before, and prior to our work, very few graph properties have been known to be testable with a constant number of queries for general graph classes in the bounded-degree graph model. [ABSTRACT FROM AUTHOR]

We study linear optimization problems over the cone of copositive matrices. These problems appear in nonconvex quadratic and binary optimization; for instance, the maximum clique problem and other combinatorial problems can be reformulated as such problems. We present new polyhedral inner and outer approximations of the copositive cone which we show to be exact in the limit. In contrast to previous approximation schemes, our approximation is not necessarily uniform for the whole cone but can be guided adaptively through the objective function, yielding a good approximation in those parts of the cone that are relevant for the optimization and only a coarse approximation in those parts that are not. Using these approximations, we derive an adaptive linear approximation algorithm for copositive programs. Numerical experiments show that our algorithm gives very good results for certain nonconvex quadratic problems. [ABSTRACT FROM AUTHOR]

We consider the offline and online versions of a bin packing problem called bin packing with conflicts. Given a set of items V = {1, 2, . . . ,n} with sizes s1, s2, . . . , sn ∈ [0, 1] and a conflict graph G = (V,E), the goal is to find a partition of the items into independent sets of G, where the total size of items in each independent set is at most 1 so that the number of independent sets in the partition is minimized. This problem is clearly a generalization of both the classical (one-dimensional) bin packing problem where E = ø and of the graph coloring problem where si = 0 for all i = 1, 2, . . . , n. Since coloring problems on general graphs are hard to approximate, following previous work, we study the problem on specific graph classes. For the offline version, we design improved approximation algorithms for perfect graphs and other special classes of graphs: These are a 5÷2 = 2.5-approximation algorithm for perfect graphs; a 7÷3 ≈ 2.33333-approximation algorithm for a subclass of perfect graphs, which contains interval graphs and chordal graphs; and a 7÷4 = 1.75-approximation for algorithm bipartite graphs. For the online problem on interval graphs, we design a 4.7-competitive algorithm and show a lower bound of 155÷36 ≈ 4.30556 on the competitive ratio of any algorithm. To derive the last lower bound, we introduce the first lower bound on the asymptotic competitive ratio of any online bin packing algorithm with known optimal value, which is 47÷36 ≈ 1.30556. [ABSTRACT FROM AUTHOR]

We consider the rooted orienteering problem: Given a set P of n points in the plane, a starting point r ∊ P, and a length constraint B, one needs to find a path starting from r that visits as many points of P as possible and of length not exceeding B. We present a (1 - ϵ)-approximation algorithm for this problem that runs in nO(1/ϵ) time; the computed path visits at least (1 - ϵ)kopt points of P, where kopt is the number of points visited by an optimal solution. This is the first polynomial time approximation scheme for this problem. The algorithm also works in higher dimensions. [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]

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]

We describe logarithmic approximation algorithms for the NP-hard graph optimization problems of minimum linear arrangement, minimum containing interval graph, and minimum storage-time product. This improves upon the best previous approximation bounds of Even, Naor, Rao, and Schieber [J. ACM, 47 (2000), pp. 585-616] for these problems by a factor of &Ohm;(log log n). We use the lower bound provided by the volume W of a spreading metric for each of the ordering problems above (as defined by Even et al.) in order to find a solution with cost at most a logarithmic factor times W for these problems. We develop a divide-and-conquer strategy where the cost of a solution to a problem at a recursive level is C plus the cost of a solution to the subproblems at this level, and where the spreading metric volume on the subproblems is less than the original volume by &Ohm;(C/log n), ensuring that the resulting solution has cost O(log n) times the original spreading metric volume. We note that this is an existentially tight bound on the relationship between the spreading metric volume and the true optimal values for these problems. For planar graphs, we combine a structural theorem of Klein, Plotkin, and Rao [Proceedings of the 25th ACM Symposium on Theory of Computing, 1993, pp. 682-690] with our new recursion technique to show that the spreading metric cost volumes are within an O(log log n) factor of the cost of an optimal solution for the minimum linear arrangement, and the minimum containing interval graph problems. [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 give a 17⁄12-approximation algorithm for the following NP-hard problem: Given a simple undirected graph, find a 2-edge connected spanning subgraph that has the minimum number of edges. The best previous approximation guarantee was 3⁄2 . If the well-known 4⁄3 conjecture for the metric traveling salesman problem holds, then the optimal value (minimum number of edges) is at most 4⁄3 times the optimal value of a linear programming relaxation. Thus our main result gets halfway to this target. [ABSTRACT FROM AUTHOR]