Search

We consider the consensus interdiction problem (CIP), in which the goal is to maximize the convergence time of consensus averaging dynamics subject to removing a limited number of network edges. We first show that CIP can be cast as an effective resistance interdiction problem (ERIP), in which the goal is to remove a limited number of network edges to maximize the effective resistance between a source node and a sink node. We show that ERIP is strongly NP-hard, even for bipartite graphs of diameter three with fixed source/sink edges, and establish the same hardness result for the CIP. We then show that both ERIP and CIP cannot be approximated up to a (nearly) polynomial factor assuming the exponential time hypothesis. Subsequently, we devise a polynomialtime mn-approximation algorithm for the ERIP that only depends on the number of nodes n and the number of edges m but is independent of the size of edge resistances. Finally, using a quadratic program formulation for the CIP, we devise an iterative approximation algorithm to find a first-order stationary solution for the CIP and evaluate its good performance through numerical experiments. [ABSTRACT FROM AUTHOR]

Persuasion, defined as the act of exploiting an informational advantage in order to inuence the decisions of others, is ubiquitous. Indeed, persuasive communication has been estimated to account for almost a third of all economic activity in the U.S. This paper examines persuasion through a computational lens, focusing on what is perhaps the most basic and fundamental model in this space: the celebrated Bayesian persuasion model of Kamenica and Gentzkow [Am. Econ. Rev., 101 (2011), pp. 2590-2615]. Here there are two players, a sender and a receiver. The receiver must take one of a number of actions with an a priori unknown payoff, and the sender has access to additional information regarding the payoffs of the various actions for both players. The sender can commit to revealing a noisy signal regarding the realization of the payoffs of various actions, and would like to do so to maximize her own payoff in expectation assuming that the receiver rationally acts to maximize his own payoff. When the payoffs of various actions follow a joint distribution (the common prior), the sender's problem is nontrivial, and its computational complexity depends on the representation of this prior. We examine the sender's optimization task in three of the most natural input models for this problem, and essentially pin down its computational complexity in each. When the payoff distributions of the different actions are independently and identically distributed (i.i.d.) and given explicitly, we exhibit a polynomial-time (exact) algorithmic solution, and a "simple" (1-1=e)-approximation algorithm. Our optimal scheme for the i.i.d. setting involves an analogy to auction theory, and makes use of Border's characterization of the space of reduced-forms for single-item auctions. When action payoffs are independent but nonidentical with marginal distributions given explicitly, we show that it is #P-hard to compute the optimal expected sender utility. In doing so, we rule out a generalized Border's theorem, in the sense of Gopalan, Nisan, and Roughgarden [Public projects, boolean functions, and the borders of Border's theorem, in Proceedings of the Sixteenth ACM Conference on Economics and Computation, EC '15, ACM, New York, 2015, p. 395], for this setting. Finally, we consider a general (possibly correlated) joint distribution of action payoffs presented by a black box sampling oracle, and exhibit a fully polynomial-time approximation scheme (FPTAS) with a bicriteria guarantee. Our FPTAS is based on Monte Carlo sampling, and its analysis relies on the principle of deferred decisions. Moreover, we show that this result is the best possible in the black-box model for information-theoretic reasons. [ABSTRACT FROM AUTHOR]

Motivated by emerging resource allocation and data placement problems such as web caches and peer-to-peer systems, we consider and study a class of resource allocation problems over a network of agents (nodes). In this model, which can be viewed as a homogeneous data placement problem, nodes can store only a limited number of resources while accessing the remaining ones through their closest neighbors. We consider this problem under both optimization and gametheoretic frameworks. In the case of optimal resource allocation, we will first show that when there are only k = 2 resources, the optimal allocation can be found efficiently in O(n ² log n) steps, where n denotes the total number of nodes. However, for k \geq 3 this problem becomes NP-hard with no polynomial-time approximation algorithm with a performance guarantee better than 1 + 1 102k², even under metric access costs. We then provide a 3-approximation algorithm for the optimal resource allocation which runs only in O(kn² ). Subsequently, we look at this problem under a selfish setting formulated as a noncooperative game and provide a 3-approximation algorithm for obtaining its pure Nash equilibria under metric access costs. We then establish an equivalence between the set of pure Nash equilibria and flip-optimal solutions of the Max-k-Cut problem over a specific weighted complete graph. While this reduction suggests that finding a pure Nash equilibrium using best response dynamics might be PLS-hard, it allows us to use tools from complementary slackness and quadratic programming to devise systematic and more efficient algorithms towards obtaining Nash equilibrium points. [ABSTRACT FROM AUTHOR]

This paper presents a weakly intrusive strategy for computing a low-rank approximation of the solution of a system of nonlinear parameter-dependent equations. The proposed strategy relies on a Newton-like iterative solver which only requires evaluations of the residual of the parameter-dependent equation and of a preconditioner (such as the differential of the residual) for instances of the parameters independently. The algorithm provides an approximation of the set of solutions associated with a possibly large number of instances of the parameters, with a computational complexity which can be orders of magnitude lower than when using the same Newton-like solver for all instances of the parameters. The reduction of complexity requires efficient strategies for obtaining low-rank approximations of the residual, of the preconditioner, and of the increment at each iteration of the algorithm. For the approximation of the residual and the preconditioner, weakly intrusive variants of the empirical interpolation method are introduced, which require evaluations of entries of the residual and the preconditioner. Then, an approximation of the increment is obtained by using a greedy algorithm for low-rank approximation, and a low-rank approximation of the iterate is finally obtained by using a truncated singular value decomposition. When the preconditioner is the differential of the residual, the proposed algorithm is interpreted as an inexact Newton solver for which a detailed convergence analysis is provided. Numerical examples illustrate the efficiency of the method. [ABSTRACT FROM AUTHOR]

In this paper, we show that every (2P2, K4)-free graph is 4-colorable. The bound is attained by the five-wheel and the complement of the seven-cycle. This answers an open question by Wagon [J. Combin. Theory Ser. B, 29 (1980), pp. 345-346] from the 1980s. Our result can also be viewed as a result in the study of the Vizing bound for graph classes. A major open problem in the study of computational complexity of graph coloring is whether coloring can be solved in polynomial time for (4P1,C4)-free graphs. Lozin and Malyshev [Discrete Appl. Math., 216 (2017), pp. 273-280] conjecture that the answer is yes. As an application of our main result, we provide the first positive evidence to the conjecture by giving a 2-approximation algorithm for coloring (4P1,C4)-free graphs. [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]

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]

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]

In the unsplittable flow problem on a path, we are given a capacitated path P and n tasks, each task having a demand, a profit, and start and end vertices. The goal is to compute a maximum profit set of tasks such that, for each edge e of P, the total demand of selected tasks that use e does not exceed the capacity of e. This is a well-studied problem that has been described under alternative names, such as resource allocation, bandwidth allocation, resource constrained scheduling, temporal knapsack, and interval packing. We present a polynomial time constant-factor approximation algorithm for this problem. This improves on the previous best known approximation ratio of O(log n). The approximation ratio of our algorithm is 7 + ∈ for any ∈ > 0. We introduce several novel algorithmic techniques, which might be of independent interest: a framework which reduces the problem to instances with a bounded range of capacities, and a new geometrically inspired dynamic program which solves to optimality a special case of the problem of finding a maximum weight independent set of rectangles. In the setting of resource augmentation, wherein the capacities can be slightly violated, we give a (2 + ∈)-approximation algorithm. In addition, we show that the problem is strongly NP-hard even if all edge capacities are equal and all demands are either 1, 2, or 3. [ABSTRACT FROM AUTHOR]

The traveling salesman problem (TSP) is a canonical NP-complete problem which is proved by Trevisan [SIAM J. Comput., 30 (2000), pp. 475-485] to be MAX-SNP hard even on high-dimensional Euclidean metrics. To circumvent this hardness, researchers have been developing approximation schemes for "simpler" instances of the problem. For instance, the algorithms of Arora and of Talwar show how to approximate TSP on low-dimensional metrics (for different notions of metric dimension). However, a feature of most current notions of metric dimension is that they are "local": the definitions require every local neighborhood to be well-behaved. In this paper, we define a global notion of dimension that generalizes the popular notion of doubling dimension, but still allows some small dense regions; e.g., it allows some metrics that contain cliques of size √n. Given a metric with global dimension dimC, we give a (1+ε)-approximation algorithm that runs in subexponential time, i.e., in exp(O(nδε-4dimC ))-time for every constant 0 < δ < 1. As mentioned above, metrics with bounded dimC may contain metrics of size O(√n) on which the TSP problem is hard to approximate to within (1 + ε). Hence, to do better than a running time of Ω(exp{√n}), our algorithms find O(1)-approximations to some portions of the tour, and (1 + ε)-approximations for other portions, and stitch them together. Moreover, we show that such globally bounded metrics have spanners that preserve distances to arbitrary accuracy and have size θ(n1.5). [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]

Given A := {a¹, . . . , am} ⊂ ℝn, we consider the problem of reducing the input set for the computation of the minimum enclosing ball of A. In this note, given an approximate solution to the minimum enclosing ball problem, we propose a simple procedure to identify and eliminate points in A that are guaranteed to lie in the interior of the minimum-radius ball enclosing A. Our computational results reveal that incorporating this procedure into two recent algorithms proposed by Yildirim lead to significant speed-ups in running times especially for randomly generated largescale problems. We also illustrate that the extra overhead due to the elimination procedure remains at an acceptable level for spherical or almost spherical input sets. [ABSTRACT FROM AUTHOR]

A cycle cover of a graph is a set of cycles such that every vertex is part of exactly one cycle. An L-cycle cover is a cycle cover in which the length of every cycle is in the set L. The weight of a cycle cover of an edge-weighted graph is the sum of the weights of its edges. We come close to settling the complexity and approximability of computing L-cycle covers. On the one hand, we show that, for almost all L, computing L-cycle covers of maximum weight in directed and undirected graphs is APX-hard. Most of our hardness results hold even if the edge weights are restricted to zero and one. On the other hand, we show that the problem of computing L-cycle covers of maximum weight can be approximated within a factor of 2 for undirected graphs and within a factor of 8/3 in the case of directed graphs. This holds for arbitrary sets L. [ABSTRACT FROM AUTHOR]

For circuit classes R, the fundamental computational problem Min-R asks for the minimum R-size of a Boolean function presented as a truth table. Prominent examples of this problem include Min-DNF, which asks whether a given Boolean function presented as a truth table has a k-term disjunctive normal form (DNF), and Min-Circuit (also called the minimum circuit size problem (MCSP)), which asks whether a Boolean function presented as a truth table has a size k Boolean circuit. We present a new reduction proving that Min-DNF is NP-complete. It is significantly simpler than the known reduction of Masek [Some NP-Complete Set Covering Problems, manuscript, 1979], which is from Circuit-SAT. We then give a more complex reduction, yielding the result that Min-DNF cannot be approximated to within a factor smaller than (log N)γ, for some constant γ > 0, assuming that NP is not contained in quasi-polynomial time. The standard greedy algorithm for Set Cover is often used in practice to approximate Min-DNF. The question of whether Min-DNF can be approximated to within a factor of o(log N) remains open, but we construct an instance of Min-DNF on which the solution produced by the greedy algorithm is Ω(log N) larger than optimal. Finally, we turn to the question of approximating circuit size for slightly more general classes of circuits. DNF formulas are depth-two circuits of AND and OR gates. Depth-d circuits are denoted by ACd0. We show that it is hard to approximate the size of ACd0 circuits (for large enough d) under cryptographic assumptions. [ABSTRACT FROM AUTHOR]

In this paper, we give the first constant-factor approximation algorithm for the rooted Orienteering problem, as well as a new problem that we call the Discounted-Reward traveling salesman problem (TSP), motivated by robot navigation. In both problems, we are given a graph with lengths on edges and rewards on nodes, and a start node s. In the Orienteering problem, the goal is to find a path starting at s that maximizes the reward collected, subject to a hard limit on the total length of the path. In the Discounted-Reward TSP, instead of a length limit we are given a discount factor γ, and the goal is to maximize the total discounted reward collected, where the reward for a node reached at time t is discounted by γt. This problem is motivated by an approximation to a planning problem in the Markov decision process (MDP) framework under the commonly employed infinite horizon discounted reward optimality criterion. The approximation arises from a need to deal with exponentially large state spaces that emerge when trying to model one-time events and nonrepeatable rewards (such as for package deliveries). We also consider tree and multiple-path variants of these problems and provide approximations for those as well. Although the unrooted Orienteering problem, where there is no fixed start node s, has been known to be approximable using algorithms for related problems such as k-TSP (in which the amount of reward to be collected is fixed and the total length is approximately minimized), ours is the first to approximate the rooted question, solving an open problem in [E. M. Arkin, J. S. B. Mitchell, and G. Narasimhan, Proceedings of the 14th ACM Symposium on Computational Geometry, 1998, pp. 307–316] and [B. Awerbuch, Y. Azar, A. Blum, and S. Vempala, SIAM J. Comput., 28 (1998), pp. 254–262]. We complement our approximation result for Orienteering by showing that the problem is APX-hard. [ABSTRACT FROM AUTHOR]

We consider the problem of computing the outer-radii of point sets. In this problem, we are given integers n, d, and k, where k ≤ d, and a set P of n points in ℜd. The goal is to compute the outer k-radius of P, denoted by Rk(P), which is the minimum over all (d - k)-dimensional flats F of maxp∊P d(p, F), where d(p, F) is the Euclidean distance between the point p and flat F. Computing the radii of point sets is a fundamental problem in computational convexity with many significant applications. The problem admits a polynomial time algorithm when the dimension d is constant [U. Faigle, W. Kern, and M. Streng, Math. Program., 73 (1996), pp. 1–5]. Here we are interested in the general case in which the dimension d is not fixed and can be as large as n, where the problem becomes NP-hard even for k = 1. It is known that Rk(P) can be approximated in polynomial time by a factor of (1 + ϵ) for any ϵ > 0 when d - k is a fixed constant [M. Bădoiu, S. Har-Peled, and P. Indyk, in Proceedings of the ACM Symposium on the Theory of Computing, 2002; S. Har-Peled and K. Varadarajan, in Proceedings of the ACM Symposium on Computing Geometry, 2002]. A polynomial time algorithm that guarantees a factor of O(√log n ) approximation for R1(P), the width of the point set P, is implied by the results of Nemirovski, Roos, and Terlaky [Math. Program., 86 (1999), pp. 463–473] and Nesterov [Handbook of Semidefinite Programming Theory, Algorithms, Kluwer Academic Publishers, Norwell, MA, 2000]. In this paper, we show that Rk(P) can be pproximated by a ratio of O(√log n ) for any 1 ≤ k ≤ d, thus matching the previously best known ratio for approximating the special case R1(P), the width of point set P. Our algorithm is based on semidefinite programming relaxation with a new mixed deterministic and randomized rounding procedure. We also prove an inapproximability result that gives evidence that our approximation algorithm is doing well for a large range of k. We show that there exists a constant δ > 0 such that the following holds for any 0 < ϵ < 1: there is no polynomial time algorithm that approximates Rk(P) within (log n)δ for all k such that k ≤ d - dϵ unless NP ⊆ DTIME [2(log m)O(1) ]. Our inapproximability result for Rk(P) extends a previously known hardness result of Brieden [Discrete Comput. Geom., 28 (2002), pp. 201–209] and is proved by modifying Brieden's construction using basic ideas from probabilistically checkable proofs (PCP) theory. [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]

We attempt to reconcile the two distinct views of approximation classes: syntactic and computational. Syntactic classes such as MAX SNP permit structural results and have natural complete problems, while computational classes such as APX allow us to work with classes of problems whose approximability is well understood. Our results provide a syntactic characterization of computational classes and give a computational framework for syntactic classes. We compare the syntactically defined class MAX SNP with the computationally defined class APX and show that every problem in APX can be "placed" (i.e., has approximation-preserving reduction to a problem) in MAX SNP. Our methods introduce a simple, yet general, technique for creating approximation-preserving reductions which shows that any "well" -approximable problem can be reduced in an approximation-preserving manner to a problem which is hard to approximate to corresponding factors. The reduction then follows easily from the recent nonapproximability results for MAX SNP-hard problems. We demonstrate the generality of this technique by applying it to other classes such as MAX SNP-RMAX(2) and MIN F[SUP+] Π[SUB2] (1) which have the clique problem and the set cover problem, respectively, as complete problems. The syntactic nature of MAX SNP was used by Papadimitriou and Yannakakis [J. Comput. System Sci., 43 (1991), pp. 425-440] to provide approximation algorithms for every problem in the class. We provide an alternate approach to demonstrating this result using the syntactic nature of MAX SNP. We develop a general paradigm, nonoblivious local search, useful for developing simple yet efficient approximation algorithms. We show that such algorithms can find good approximations for all MAX SNP problems, yielding approximation ratios comparable to the best known for a variety of specific MAX SNP-hard problems. [ABSTRACT FROM AUTHOR]