Search

We present a general technique for the analysis of first-order methods. The technique relies on the construction of a duality gap for an appropriate approximation of the objective function, where the function approximation improves as the algorithm converges. We show that in continuous time the enforcement of an invariant, which corresponds to the approximate duality gap decreasing at a certain rate, exactly recovers a wide range of first-order continuous-time methods. We characterize the discretization errors incurred by different discretization methods, and show how iteration-complexity-optimal methods for various classes of problems cancel out the discretization error. The techniques are illustrated on various classes of problems--including convex minimization for Lipschitz-continuous objectives, smooth convex minimization, composite minimization, smooth and strongly convex minimization, solving variational inequalities with monotone operators, and convex-concave saddle-point optimization--and naturally extend to other settings. [ABSTRACT FROM AUTHOR]

In stochastic programming, statistics, or econometrics, the aim is in general the optimization of a criterion function that depends on a decision variable ϑ and reads as an expectation with respect to a probability P. When this function cannot be computed in closed form, it is customary to approximate it through an empirical mean function based on a random sample. On the other hand, several other methods have been proposed, such as quasi-Monte Carlo integration and numerical integration rules. In this paper, we propose a general approach for approximating such a function, in the sense of epigraphical convergence, using a sequence of functions of simpler type which can be expressed as expectations with respect to probability measures Pn's that, in some sense, approximate P. The main difference with the existing results lies in the fact that our main theorem does not impose conditions directly on the approximating probabilities but only on some integrals with respect to them. In addition, the Pn's can be transition probabilities, i.e., are allowed to depend on a further parameter, ξ, whose value results from deterministic or stochastic operations, depending on the underlying model. This framework allows us to deal with a large variety of approximation procedures such as Monte Carlo, quasi--Monte Carlo, numerical integration, quantization, several variations on Monte Carlo sampling, and some density approximation algorithms. As by-products, we discuss convergence results for stochastic programming and statistical inference based on dependent data, for programming with estimated parameters, and for robust optimization; we also provide a general result about the consistency of the bootstrap for M-estimators. [ABSTRACT FROM AUTHOR]

We consider the maximum vertex-weighted matching problem (MVM), in which nonnegative weights are assigned to the vertices of a graph, the weight of a matching is the sum of the weights of the matched vertices, and we are required to compute a matching of maximum weight. We describe an exact algorithm for MVM with O(| V | | E| ) time complexity, and then we design a 2/3-approximation algorithm for MVM on bipartite graphs by restricting the length of augmenting paths to at most three. The latter algorithm has time complexity O(| E| +| V | log | V | ). The approximation algorithm solves two MVM problems on bipartite graphs, each with weights only on one vertex part, and then finds a matching from these two matchings using the Mendelsohn--Dulmage theorem. The approximation ratio of the algorithm is obtained by considering failed vertices, i.e., vertices that the approximation algorithm fails to match but the exact algorithm does. We show that at every step of the algorithm there are two distinct heavier vertices that we can charge each failed vertex to. We have implemented the 2/3-approximation algorithm for MVM and compare it with four other algorithms: an exact maximum edge-weighted matching (MEM) algorithm, the exact MVM algorithm, a 1/2-approximation algorithm for MVM, and a scaling-based (1 - ϵ)-approximation algorithm for MEM. On a test set of nineteen problems with several millions of vertices, we show that the maximum time taken by the exact MEM algorithm is 15 hours, while it is 22 minutes for the exact MVM algorithm, and less than 5 seconds for the 2/3-approximation algorithm. The 2/3-approximation algorithm obtains more than 99.5% of the weight and cardinality of an MVM, whereas the scaling-based approximation algorithms yield lower weights and cardinalities while taking an order of magnitude more time than the former algorithm. We also show that MVM problems should not be first transformed to MEM problems and solved using exact algorithms for the latter, since this transformation can increase runtimes by several orders of magnitude [ABSTRACT FROM AUTHOR]

We present several approximation algorithms for the problem of embedding metric spaces into a line, and into the 2-dimensional plane. Among other results, we give an O(√n)- approximation algorithm for the problem of finding a line embedding of a metric induced by a given unweighted graph, that minimizes the (standard) multiplicative distortion. We give an improved Õ(n1/3) approximation for the case of metrics induced by unweighted trees. [ABSTRACT FROM AUTHOR]

In this paper, we show that the popular K-means clustering problem can equivalently be reformulated as a conic program of polynomial size. The arising convex optimization problem is NP-hard, but amenable to a tractable semidefinite programming (SDP) relaxation that is tighter than the current SDP relaxation schemes in the literature. In contrast to the existing schemes, our proposed SDP formulation gives rise to solutions that can be leveraged to identify the clusters. We devise a new approximation algorithm for K-means clustering that utilizes the improved formulation and empirically illustrate its superiority over the state-of-the-art solution schemes. [ABSTRACT FROM AUTHOR]

We study the mathematical concept of the strength of a graph as defined by Cunningham to partition very large graphs. The strength is the objective value of an attack problem on a graph where the striker aims at dividing the graph into a maximum number of connected components removing as few edges as possible per component uncoupled. The strength is the optimal number of edges per component uncoupled or, in the weighted version, the sum of the weights of the edges removed per component uncoupled. Given a connected graph with n vertices and m weighted edges, we denote by W the total sum of the integer weights, and we describe an algorithm that approximates within a factor of 1+ε the weighted strength in time O(mlog(W)log³(n)/ε²), and that can be implemented with O(m) memory use if we allow a complexity of O(mlog²(W)log³(n)/ε²). This result has several important applications, in particular for the detection of dense areas of a graph, in terms of weighted edges, which in turn can be used for spam detection, community identification, and partitioning. [ABSTRACT FROM AUTHOR]

We study a semide finite programming relaxation of the traveling salesman problem introduced by de Klerk, Pasechnik, and Sotirov [SIAM J. Optim., 19 (2008), pp. 1559{1573] and show that their relaxation has an unbounded integrality gap. In particular, we give a family of instances such that the gap increases linearly with n. To obtain this result, we search for feasible solutions within a highly structured class of matrices; the problem of finding such solutions reduces to finding feasible solutions for a related linear program, which we do analytically. The solutions we find imply the unbounded integrality gap. Further, these solutions imply several corollaries that help us better understand the semidefinite program and its relationship to other TSP relaxations. Using the same technique, we show that a more general semidefinite program introduced by de Klerk, de Oliveira Filho, and Pasechnik [Handbook on Semidefinite, Conic and Polynomial Optimization, Springer, New York, 2012, pp. 171{199.] for the k-cycle cover problem also has an unbounded integrality gap. [ABSTRACT FROM AUTHOR]

Randomized algorithms for low-rank matrix approximation are investigated, with the emphasis on the fixed-precision problem and computational efficiency for handling large matrices. The algorithms are based on the so-called QB factorization, where Q is an orthonormal matrix. First, a mechanism for calculating the approximation error in the Frobenius norm is proposed, which enables efficient adaptive rank determination for a large and/or sparse matrix. It can be combined with any QB-form factorization algorithm in which B's rows are incrementally generated. Based on the blocked randQB algorithm by Martinsson and Voronin, this results in an algorithm called randQB EI. Then, we further revise the algorithm to obtain a pass-efficient algorithm, randQB FP, which is mathematically equivalent to the existing randQB algorithms and also suitable for the fixed-precision problem. Especially, randQB FP can serve as a single-pass algorithm for calculating leading singular values, under a certain condition. With large and/or sparse test matrices, we have empirically validated the merits of the proposed techniques, which exhibit remarkable speedup and memory saving over the blocked randQB algorithm. We have also demonstrated that the single-pass algorithm derived by randQB FP is much more accurate than an existing single-pass algorithm. And with data from a scenic image and an information retrieval application, we have shown the advantages of the proposed algorithms over the adaptive range finder algorithm for solving the fixed-precision problem. [ABSTRACT FROM AUTHOR]

The Chordal Vertex Deletion (CHVD) problem asks to delete a minimum number of vertices from an input graph to obtain a chordal graph. In this paper we develop a polynomial kernel for CHVD under the parameterization by the solution size. Using a new Erdõs-Pósa-type packing/covering duality for holes in nearly chordal graphs, we present a polynomial-time algorithm that reduces any instance (G, k) of CHVD to an equivalent instance with poly(k) vertices. The existence of a polynomial kernel answers an open problem posed by Marx in 2006 [D. Marx, "Chordal Deletion Is Fixed-Parameter Tractable," in Graph-Theoretic Concepts in Computer Science, Lecture Notes in Comput. Sci. 4271, Springer, 2006, pp. 37-48]. To obtain the kernelization, we develop the first poly(opt)-approximation algorithm for CHVD, which is of independent interest. In polynomial time, it either decides that G has no chordal deletion set of size k, or outputs a solution of size O(k4log² k). [ABSTRACT FROM AUTHOR]

We study scheduling problems on a machine with varying speed. Assuming a known speed function we ask for a cost-efficient scheduling solution. Our main result is a polynomial-time approximation scheme (PTAS) for minimizing the total weighted completion time in this setting. This also implies a PTAS for the closely related problem of scheduling to minimize generalized global cost functions, that is, the problem 1||wjf(Cj). The key to our results is a reinterpretation of the problem within the well-known two-dimensional Gantt chart: instead of the standard approach of scheduling in the time dimension, we construct scheduling solutions in the weight dimension. This allows structural simplifications of the instance and optimal solutions, based on which we can defer the concern of speed to the evaluation of cost in a dynamic programming framework. We also consider a dynamic problem variant, where the decision upon the speed is part of the problem and we are interested in the trade-off between scheduling cost and speed-scaling cost, which is typically the energy consumption. We observe that the optimal order is independent of the energy consumption and that the problem can be reduced to the setting where the speed of the machine is fixed, and thus admits a PTAS. Furthermore, we provide a fully polynomial-time approximation scheme for the NPhard problem variant in which the machine can run only at a fixed number of discrete speeds. Finally, we show how our results can be used to obtain a (2 + ε)-approximation for scheduling preemptive jobs with release dates on multiple identical parallel machines. [ABSTRACT FROM AUTHOR]

The Euler genus of a graph is a fundamental and well-studied parameter in graph theory and topology. Computing it has been shown to be NP-hard by Thomassen [J. Algorithms, 10 (1989), pp. 568{576; J. Combin. Theory, Ser. B, 57 (1993), pp. 196{206], and it is known to be fixed-parameter tractable. However, the approximability of the Euler genus is wide open. While the existence of an O(1)-approximation is not ruled out, only an O( p n)-approximation [J. Chen, S. P. Kanchi, and A. Kanevsky, Inform. Process. Lett., 61 (1997), pp. 317{322] is known even in bounded-degree graphs. In this paper we give a polynomial-time algorithm which, given a boundeddegree graph of Euler genus g, computes a drawing in a surface of Euler genus gO(1) · logO(1) n. Combined with the upper bound from [J. Chen, S. P. Kanchi, and A. Kanevsky, Inform. Process. Lett., 61 (1997), pp. 317{322], our result also implies a O(n1/2-α)-approximation for some constant α > 0. Using our algorithm for approximating the Euler genus as a subroutine, we obtain, in a uniform fashion, algorithms with approximation ratios of the form OPTO(1) · logO(1) n for several related problems on bounded-degree graphs. These include the problems of orientable genus, crossing number, and planar edge and vertex deletion. Our algorithm and proof of correctness for the crossing number problem are simpler compared to the long and difficult proof in the recent breakthrough by Chuzhoy [Proceedings of the ACM Symposium on Theory of Computing, 2011, pp. 303{312], while essentially obtaining a qualitatively similar result. For planar edge and vertex deletion problems our results are the first to obtain a bound of the form poly(OPT; log n). We also highlight some further applications of our results in the design of algorithms for graphs with small genus. Many such algorithms require that a drawing of the graph is given as part of the input. Our results imply that in several interesting cases, we can implement such algorithms even when the drawing is unknown. [ABSTRACT FROM AUTHOR]

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]

In this paper, we present a new monotone approximation of a given real-valued Carathéodory function on the product X × A of Borel spaces, where A is also compact. We demonstrate its application by providing a self-contained and elementary proof of a result of A. Nowak in discrete-time Markov decision processes. [ABSTRACT FROM AUTHOR]

We derive some characterizations of probability distributions for linear forms of Q-independent random variables. [ABSTRACT FROM AUTHOR]

We study the problem of allocating a set of indivisible items among agents with additive valuations, with the goal of maximizing the geometric mean of the agents' valuations, i.e., the Nash social welfare. This problem is known to be NP-hard, and our main result is the first efficient constant-factor approximation algorithm for this objective. We first observe that the integrality gap of the natural fractional relaxation is exponential, so we propose a different fractional allocation which implies a tighter upper bound and, after appropriate rounding, yields a good integral allocation. An interesting contribution of this work is the fractional allocation that we use. The relaxation of our problem can be solved efficiently using the Eisenberg--Gale program, whose optimal solution can be interpreted as a market equilibrium with the dual variables playing the role of item prices. Using this market-based interpretation, we define an alternative equilibrium allocation where the amount of spending that can go into any given item is bounded, thus keeping the highly priced items underallocated and forcing the agents to spend on lower priced items. The resulting equilibrium prices reveal more information regarding how to assign items so as to obtain a good integral allocation. [ABSTRACT FROM AUTHOR]

In the submodular welfare maximization (SWM) problem, the input consists of a set of n items, each of which must be allocated to one of m agents. Each agent l has a valuation function vl, where vl(S) denotes the welfare obtained by this agent if she receives the set of items S. The functions vl are all submodular; as is standard, we assume that they are monotone and vl(Φ) = 0. The goal is to partition the items into m disjoint subsets S1; S2, ..., Sm in order to maximize the so-cial welfare, defined as .... A simple greedy algorithm gives a 1/2-approximation to SWM in the offline setting, and this was the best known until Vondrák's recent (1 - 1/e)-approximation algorithm [Optimal approximation for the submodular welfare problem in the value oracle model, in Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing (STOC '08), ACM, 2008, pp. 67-74]. In this paper, we consider the online version of SWM. Here, items arrive one at a time in an online manner; when an item arrives, the algorithm must make an irrevocable decision about which agent to assign it to before seeing any subsequent items. This problem is motivated by applications to Internet advertising, where user ad impressions must be allocated to advertisers whose value is a submodular function of the set of users/impressions they receive. There are two natural models that differ in the order in which items arrive. In the fully adversarial setting, an adversary can construct an arbitrary/worst-case instance, as well as pick the order in which items arrive in order to minimize the algorithm's performance. In this setting, the 1/2-competitive greedy algorithm is the best possible. To improve on this, one must weaken the adversary slightly: In the random order model, the adversary can construct a worst-case set of items and valuations but does not control the order in which the items arrive; instead, they are assumed to arrive in a random order. The random order model has been well studied for online SWM and various special cases, but the best known competitive ratio (even for several special cases) is 1/2+1=n, which is barely better than the ratio for the adversarial order [S. Dobzinski, N. Nisan, and M. Schapira, Math. Oper. Res., 35 (2010), pp. 1-13; S. Dobzinski and M. Schapira, An improved approximation algorithm for com-binatorial auctions with submodular bidders, in Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '06), ACM; SIAM, 2006, pp. 1064-1073]. Obtaining a competitive ratio of 1/2 + Ω(1) for the random order model has been an important open problem for several years. We solve this open problem by demonstrating that the greedy algorithm has a competitive ratio of at least 0:505 for online SWM in the random order model. This is the first result showing a competitive ratio bounded above 1/2 in the random order model, even for special cases such as the weighted matching or budgeted allocation problem (without the so-called large capac-ity assumptions). For special cases of submodular functions including weighted matching, weighted coverage functions, and a broader class of "second-order supermodular" functions, we provide a different analysis that gives a competitive ratio of 0.51. We analyze the greedy algorithm using a factor-revealing linear program, bounding how the assignment of one item can decrease potential welfare from assigning future items. In addition to our new competitive ratios for online SWM, we make two further contributions: First, we define the classes of second-order modular, supermodular, and submodular functions, which are likely to be of independent interest in submodular optimiza-tion. Second, we obtain an improved competitive ratio via a technique we refer to as gain linearizing, which may be useful in other contexts (see [V. S. Mirrokni and M. Zadimoghaddam, Randomized composable core-sets for distributed submodular maximization, in Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing (STOC '15), ACM, 2015, pp. 153-162]): Essen-tially, we linearize the submodular function by dividing the gain of an optimal solution into gain from individual elements, compare the algorithm's gain when it assigns an element to the optimal solution's gain from the element, and, crucially, bound the extent to which assigning elements can affect the potential gain of other elements. [ABSTRACT FROM AUTHOR]

Metric data structures (distance oracles, distance labeling schemes, routing schemes) and low-distortion embeddings provide a powerful algorithmic methodology, which has been success-fully applied for approximation algorithms [N. Linial, E. London, and Y. Rabinovich, Combinatorica, 15 (1995), pp. 215-245], online algorithms [N. Bansal et al., Proceedings of the 52th Annual IEEE Symposium on Foundations of Computer Science, FOCS '08, IEEE Computer Society, Washington, DC, 2011, pp. 267-276], distributed algorithms [M. Khan et al., Distrib. Comput., 25 (2012), pp. 189-205], and for computing sparsifiers [Y. Shavitt and T. Tankel, IEEE/ACM Trans. Netw., 12 (2004), pp. 993-1006]. However, this methodology appears to have a limitation: the worst-case performance inherently depends on the cardinality of the metric, and one could not specify in advance which vertices/points should enjoy a better service (i.e., stretch/distortion, label size/dimension) than that given by the worst-case guarantee. In this paper we alleviate this limitation by devising a suite of prioritized metric data structures and embeddings. We show that given a priority ranking (x1; x2; ..., xn) of the graph vertices (resp., metric points) one can devise a metric data structure (resp., embedding) in which the stretch (resp., distortion) incurred by any pair containing a vertex xj will depend on the rank j of the vertex. We also show that other important parameters, such as the label size and (in some sense) the dimension, may depend only on j. In some of our metric data structures (resp., embeddings) we achieve both prioritized stretch (resp., distortion) and label size (resp., dimension) simultaneously. The worst-case performance of our metric data structures and embeddings is typically asymptotically no worse than of their nonprioritized counterparts. [ABSTRACT FROM AUTHOR]

We study the metric s--t path traveling salesman problem (TSP). An, Kleinberg, and Shmoys [Proceedings of the 44th ACM Symposium on Theory of Computing, 2012, pp. 875-886] improved on the long-standing 5/3 -approximation factor and presented an algorithm that achieves an approximation factor of 1+√5/2 ≈ 1.61803. Later, Sebö [Proceedings of the 16th Conference on Integer Programming and Combinatorial Optimization, 2013, pp. 362-374] further improved the approximation factor to 8/5. We present a simple, self-contained analysis that unifies both results; our main contribution is a unified correction vector. Additionally, we compare two different linear programming (LP) relaxations of the s--t path TSP, namely, the path version of the Held--Karp LP relaxation for the TSP and a weaker LP relaxation, and we show that both LPs have the same (fractional) optimal value. Also, we show that the minimum cost of integral solutions of the two LPs are within a factor of 3/2 of each other. Furthermore, we prove that a half-integral solution of the stronger LP relaxation of cost c can be rounded to an integral solution of cost at most 3/2 c. Finally, we give an example that presents obstructions to two natural methods that aim for an approximation factor of 3/2. [ABSTRACT FROM AUTHOR]

We investigate problems addressing combined connectivity augmentation and orientations settings. We give a polynomial-time 6-approximation algorithm for finding a minimum cost subgraph of an undirected graph G that admits an orientation covering a nonnegative crossing G-supermodular demand function, as defined by Frank [J. Comb. Theory Ser. B, 28 (1980), pp. 251-261]. An important example is (k; ℓ)-edge-connectivity, a common generalization of global and rooted edge-connectivity. Our algorithm is based on a nonstandard application of the iterative rounding method. We observe that the standard linear program with cut constraints is not amenable and use an alternative linear program with partition and copartition constraints instead. The proof requires a new type of uncrossing technique on partitions and copartitions. We also consider the problem setting when the cost of an edge can be different for the two possible orientations. The problem becomes substantially more difficult already for the simpler requirement of k-edge-connectivity. Khanna, Naor, and Shepherd [SIAM J. Discrete Math., 19 (2005), pp. 245-257] showed that the integrality gap of the natural linear program is at most 4 when k = 1 and conjectured that it is constant for all fixed k. We disprove this conjecture by showing Ω (|V |) integrality gap even when k = 2. [ABSTRACT FROM AUTHOR]

In the polytope membership problem, a convex polytope K in Rd is given, and the objective is to preprocess K into a data structure so that, given any query point q 2 Rd, it is possible to determine efficiently whether q ∊ K. We consider this problem in an approximate setting. Given an approximation parameter ε, the query can be answered either way if the distance from q to K's boundary is at most ε times K's diameter. We assume that the dimension d is fixed, and K is presented as the intersection of n halfspaces. Previous solutions to approximate polytope membership were based on straightforward applications of classic polytope approximation techniques by Dudley [Approx. Theory, 10 (1974), pp. 227-236] and Bentley, Faust, and Preparata [Commun. ACM, 25 (1982), pp. 64-68]. The former is optimal in the worst case with respect to space, and the latter is optimal with respect to query time. We present four main results. First, we show how to combine the two above techniques to obtain a simple space-time trade-off. Second, we present an algorithm that dramatically improves this trade-off. In particular, for any constant α ≥ 4, this data structure achieves query time roughly O(1/ε(d-1)/α) and space roughly O(1=ε(d-1)(1-Ω(log α)=α)). We do not know whether this space bound is tight, but our third result shows that there is a convex body such that our algorithm achieves a space of at least Ω (1/εd-1)(1-O(√α)α). Our fourth result shows that it is possible to reduce approximate Euclidean nearest neighbor searching to approximate polytope membership queries. Combined with the above results, this provides significant improvements to the best known space-time trade-offs for approximate nearest neighbor searching in Rd. For example, we show that it is possible to achieve a query time of roughly O(log n + 1=εd/4) with space roughly O(n/εd/4), thus reducing by half the exponent in the space bound. [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 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]

In this paper we show a new way of constructing deterministic polynomial-time approximation algorithms for computing complex-valued evaluations of a large class of graph polynomials on bounded degree graphs. In particular, our approach works for the Tutte polynomial and independence polynomial, as well as partition functions of complex-valued spin and edge-coloring models. More specifically, we define a large class of graph polyn omials C and show that if p € C and there is a disk D centered at zero in the complex plane such that p(G) does not vanish on D for all bounded degree graphs G, then for each z in the interior of D there exists a deterministic polynomialtime approximation algorithm for evaluating p(G) at z. This gives an explicit connection between absence of zeros of graph polynomials and the existence of efficient approximation algorithms, allowing us to show new relationships between well-known conjectur es. Our work builds on a recent line of work initiated by Barvinok [Found. Comput. Math., 16 (20 16), pp. 329--342; Theory Comput., 11 (2015), pp. 339--355; Computing the Partition Function of a Polynomial on the Boolean Cube, 2015; Discrete Anal., 2 (2017), 34pp], which provides a new algorithmic approach besides the existing Markov chain Monte Carlo method and the correlation decay method for these types of problems. [ABSTRACT FROM AUTHOR]

We investigate the family of intersection graphs of low density objects in low dimensional Euclidean space. This family is quite general, includes planar graphs, and in particular is a subset of the family of graphs that have polynomial expansion. We present efficient (1+ε)-approximation algorithms for polynomial expansion graphs for unweighted Independent Set, Set Cover, and Dominating Set problems, among others, and these results seem to be new. Naturally, PTASs for these problems are known for subclasses of this graph family. These results have immediate applications in the geometric domain. For example, the new algorithms yield the only PTAS known for covering points by fat triangles (that are shallow). We also prove corresponding hardness of approximation for some of these optimization problems, characterizing their intractability with respect to density. For example, we show that there is no PTAS for covering points by fat triangles if they are not shallow, thus matching our PTAS for this problem with respect to depth. [ABSTRACT FROM AUTHOR]

In recent work by the authors [I. Noad and R. Porter, Renewable Energy, 114 (2017), pp. 1146--1159], the problem of absorption of ocean wave energy by a floating articulated raft was studied. Numerical computations were shown to be rapid under a wide range of configurations but became increasingly expensive in certain limits. These included rafts either wide or narrow with respect to the incident wave direction and rafts with many articulations. The current paper proposes approximations to each of these cases resulting in a significant reduction in the numerical effort required. Typical computations are more than 100 times faster in the case of the wide or narrow raft approximations, and it is shown that a simplified continuum model for an articulated raft predicts power absorption with less than a 1% error for rafts with three or more articulations. [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]

We consider the problem of estimating the number of triangles in a graph. This problem has been extensively studied in both theory and practice, but all existing algorithms read the entire graph. In this work we design a sublinear-time algorithm for approximating the number of triangles in a graph, where the algorithm is given query access to the graph. The allowed queries are degree queries, vertex-pair queries, and neighbor queries. We show that for any given approximation parameter 0 < ε < 1, the algorithm provides an estimate t such that, with high constant probability, (1 - ε). t < t < (1 + ε). t, where t is the number of triangles in the graph G. The expected query complexity of the algorithm is ... poly(log n, 1/ε), where n is the number of vertices in the graph and m is the number of edges. The expected running time of the algorithm is ... poly(log n, 1/ε). We also prove that ... queries are necessary, thus establishing that the query complexity of this algorithm is optimal up to the dependence on poly (log n, 1/ε). [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 present a numerical method for polynomial approximation of multivariate functions. The method utilizes Gauss quadrature in tensor product form, which is known to be inefficient in high dimensions. Here we demonstrate that by using a new randomized algorithm and taking advantage of the tensor structure of the grids, a highly efficient algorithm can be constructed. The new method does not require prior knowledge/storage of the entire data set at all the tensor grid points, whose total number of points is excessively large in high dimensions. Instead the method utilizes one data point at a time and iteratively conducts the approximation. This feature allows the use of the method irrespective of the size of the data set. We establish the rate of convergence of this iterative algorithm and show that its operational counts can be lower than the standard methods, when applicable, such as least squares. Numerical examples in up to hundreds of dimensions are presented to verify the theoretical analysis and demonstrate the effectiveness of the method. [ABSTRACT FROM AUTHOR]

In this paper we develop a two-grid convergence theory for the parallel-in-time scheme known as multigrid reduction in time (MGRIT), as it is implemented in the open-source package [XBraid: Parallel Multigrid in Time, http://llnl.gov/casc/xbraid]. MGRIT is a scalable and multilevel approach to parallel-in-time simulations that nonintrusively uses existing time-stepping schemes, and in a specific two-level setting it is equivalent to the widely known parareal algorithm. The goal of this paper is twofold. First, we present a two-level MGRIT convergence analysis for linear problems where the spatial discretization matrix can be diagonalized, and then apply this analysis to our two basic model problems, the heat equation and the advection equation. One important assumption is that the coarse and fine time-grid propagators can be diagaonalized by the same set of eigenvectors, which is often the case when the same spatial discretization operator is used on the coarse and fine time grids. In many cases, the MGRIT algorithm is guaranteed to converge, and we demonstrate numerically that the theoretically predicted convergence rates are sharp in practice for our model problems. Second, we explore how the convergence of MGRIT compares to the stability of the chosen time-stepping scheme. In particular, we demonstrate that a stable time-stepping scheme does not necessarily imply convergence of MGRIT, although MGRIT with FCF-relaxation always converges for the diffusion dominated problems considered here. [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 present a 10/7 -approximation algorithm for the minimum 2-vertex-connected spanning subgraph problem. Similarly to the work of Cheriyan, Sebö, and Szigeti for 2-edge-connected spanning subgraphs, our algorithm is based on computing a carefully designed ear-decomposition. [ABSTRACT FROM AUTHOR]

Given an undirected graph G = (VG,EG) and a fixed "pattern" graph H = (VH,EH) with k vertices, we consider the H-Transversal and H-Packing problems. The former asks to find the smallest S ⊆ VG such that the subgraph induced by VG \ S does not have H as a subgraph, and the latter asks to find the maximum number of pairwise disjoint k-subsets S1,...,Sm ⊆ VG such that the subgraph induced by each Si has H as a subgraph. We prove that if H is 2-connected, H-Transversal and H-Packing are almost as hard to approximate as general k-Hypergraph Vertex Cover and k-Set Packing, so it is NP-hard to approximate them within a factor of Ω(k) and Ω(k), respectively. We also show that there is a 1-connected H where H-Transversal admits an O(log k)-approximation algorithm, so that the connectivity requirement cannot be relaxed from 2 to 1. For a special case of H-Transversal where H is a (family of) cycles, we mention the implication of our result to the related Feedback Vertex Set problem and give a different hardness proof for directed graphs. [ABSTRACT FROM AUTHOR]

We propose a projection-based model order reduction method for the solution of parameter-dependent dynamical systems. The proposed method relies on the construction of timedependent reduced spaces generated from evaluations of the solution of the full-order model at some selected parameter values. The approximation obtained by Galerkin projection is the solution of a reduced dynamical system with a modified ux that takes into account the time dependency of the reduced spaces. An a posteriori error estimate is derived, and a greedy algorithm using this error estimate is proposed for the adaptive selection of parameter values. The resulting method can be interpreted as a dynamical low-rank approximation method with a subspace point of view and a uniform control of the error over the parameter set. [ABSTRACT FROM AUTHOR]

A crude but commonly used technique for compressing ordered scientific data consists of simply retaining every sth datum (with a value of s = 10 generally the default) and discarding the remainder. Should the value of a discarded datum be required afterwards, an approximation is generated by linear interpolation of the two nearest retained values. Despite the widespread use of this and similar techniques, there is little by way of theoretical analysis of their expected performance. First, we quantify the accuracy achieved by linear interpolation when approximating values discarded by decimation, obtaining both deterministic bounds in terms of appropriate smoothness measures of the data and probabilistic bounds in terms of statistics of the data. Second, we investigate the efficiency of the lossless compression scheme consisting of decimation coupled with encoding of the interpolation errors. In particular, we bound the expected compression ratio in terms of the appropriate measures of the data. Finally, we provide numerical illustrations of the practical performance of the algorithm on some real datasets. [ABSTRACT FROM AUTHOR]

Functions with jumps and kinks typically arising from parameter dependent or stochastic hyperbolic PDEs are notoriously difficult to approximate. If the jump location in physical space is parameter dependent or random, standard approximation techniques like reduced basis methods, PODs, polynomial chaos, etc., are known to yield poor convergence rates. In order to improve these rates, we propose a new approximation scheme. It relies on snapshots for the reconstruction of parameter dependent functions so that it is efficiently applicable in a PDE context. However, the physical domain of each individual snapshot is transformed before its use in the recon- struction, which allows realignng the moving discontinuities and yields high convergence rates. The transforms are automatically computed by minimizing a training error. In order to show feasibility of this approach, it is tested by numerical experiments with one and two physical dimensions and one parameter dimension. [ABSTRACT FROM AUTHOR]

We propose and compare goal-oriented projection-based model order reduction meth- ods for the estimation of vector-valued functionals of the solution of parameter-dependent equations. The first projection method is a generalization of the classical primal-dual method to the case of vector-valued variables of interest. We highlight the role played by three reduced spaces: the ap- proximation space and the test space associated to the primal variable, and the approximation space associated with the dual variable. Then we propose a Petrov-Galerkin projection method based on a saddle point problem involving an approximation space for the primal variable and an approximation space for an auxiliary variable. A goal-oriented choice of the latter space, defined as the sum of two spaces, allows us to improve the approximation of the variable of interest compared to a primal-dual method using the same reduced spaces. Then, for both approaches, we derive computable error estimates for the approximations of the variable of interest and we propose greedy algorithms for the goal-oriented construction of reduced spaces. The performance of the algorithms is illustrated on numerical examples and compared to standard (non-goal-oriented) algorithms. [ABSTRACT FROM AUTHOR]

Proper generalized decompositions (PGDs) are a family of methods for efficiently solving high-dimensional PDEs, which seek to find a low-rank approximation to the solution of the PDE a priori. Convergence of PGD algorithms can only be proven for problems which are continuous, symmetric, and strongly coercive. In the particular case of problems which are only weakly coercive we have the additional issue that weak coercivity estimates are not guaranteed to be inherited by the low-rank PGD approximation. This can cause stability issues when employing a Galerkin PGD approximation of weakly coercive problems. In this paper we propose the use of PGD algorithms based on least-squares formulations which always lead to symmetric and strongly coercive problems and hence provide stable and provably convergent algorithms. Taking the Stokes problem as a prototypical example of a weakly coercive problem, we develop and compare rigorous leastsquares PGD algorithms based on continuous least-squares estimates for two different reformulations of the problem. We show that these least-squares PGDs provide a much stabler algorithm than an equivalent Galerkin PGDs, and we provide proofs of convergence of the algorithms. [ABSTRACT FROM AUTHOR]

We construct and analyze acceleration techniques for adaptive Monte Carlo simulations for general multivariate probability laws when the sample average approximation is employed for optimal parameter search. Our goal is to accelerate the adaptive Monte Carlo estimation by lead- ing the parameter search line based on the sample average approximation to reach a nearly optimal realm at its small sample size stage. First, we introduce an auxiliary parameter into the parameter search line and update it wisely to aim for small-sample convergence. All three lines of the algorithm (the Monte Carlo averaging, the importance sampling parameter search, and the auxiliary parame- ter updating) run concurrently in a fully automated manner with a common set of random vectors without ad hoc tuning of the simulation system. We next propose and examine various criteria for the auxiliary parameter updating, all under which the asymptotic normality of the estimator of the desired mean and of the importance sampling parameter hold true. To illustrate the applicability and effectiveness of the proposed methods, we provide numerical results throughout the paper with particular attention toward the very early stages of the algorithm. In particular, direct use of the importance sampling parameter as the auxiliary parameter has the great potential to accelerate the parameter search line, and thus the Monte Carlo averaging as a consequence, by orders of magnitude without further restriction of the parameter domain or additional computing effort. [ABSTRACT FROM AUTHOR]

We give a simple, randomized greedy algorithm for the maximum satisfiability problem (MAX SAT) that obtains a ¾ -approximation in expectation. In contrast to previously known ¾ -approximation algorithms, our algorithm does not use flows or linear programming. Hence we provide a positive answer to a question posed byWilliamson in 1998 on whether such an algorithm exists. Moreover, we show that Johnson's greedy algorithm cannot guarantee a ¾ -approximation, even if the variables are processed in a random order. Thereby we partially solve a problem posed by Chen, Friesen, and Zheng in 1999. In order to explore the limitations of the greedy paradigm, we use the model of priority algorithms of Borodin, Nielsen, and Rackoff. Since our greedy algorithm works in an online scenario where the variables arrive with their set of undecided clauses, we wonder if a better approximation ratio can be obtained by further fine-tuning its random decisions. For a particular information model we show that no priority algorithm can approximate Online MAX SAT within ¾ + ε (for any ε > 0). We further investigate the strength of deterministic greedy algorithms that may choose the variable ordering. Here we show that no adaptive priority algorithm can achieve approximation ratio ¾ . We propose two ways in which this inapproximability result can be bypassed. First we show that if our greedy algorithm is additionally given the variable assignments of an optimal solution to the canonical LP relaxation, then we can derandomize its decisions while preserving the overall approximation guarantee. Second we give a simple, deterministic algorithm that performs an additional pass over the input. We show that this 2-pass algorithm satisfies clauses with a total weight of at least ¾OPTLP, where OPTLP is the objective value of the canonical linear program. Moreover, we demonstrate that our analysis is tight and detail how each pass can be implemented in linear time. [ABSTRACT FROM AUTHOR]

The Unique Coverage problem, given a universe V of elements and a collection E of subsets of V , asks to find S ⊆ V to maximize the number of e ∈ E that intersects S in exactly one element. When each de ∈ E has cardinality at most k, it is also known as 1-in-k Hitting Set and admits a simple Ω( 1/ log k )-approximation algorithm. For constant k, we prove that 1-in-k Hitting Set is NP-hard to approximate within a factor O( 1/ log k ). This improves the result of Guruswami and Zhou [Theory Comput., 8 (2012), pp. 239-267], who proved the same result assuming the Unique Games Conjecture. For Unique Coverage, we prove that it is hard to approximate within a factor O( 1/log1-∊ n ) for any ∊ > 0, unless NP admits quasi-polynomial time algorithms. This improves the results of Demaine et al. [SIAM J. Comput., 38 (2008), pp. 1464-1483], including their ≈ 1/ log1/3 n inapproximability factor, which was proven under the Random 3SAT Hypothesis. Our simple proof combines ideas from two classical inapproximability results for the Set Cover and Constraint Satisfaction Problems, made efficient by various derandomization methods based on bounded independence. [ABSTRACT FROM AUTHOR]

We study a fundamental measure for wireless interference in the signal-to-interference noise ratio model known as (weighted) inductive independence. This measure characterizes the effectiveness of using oblivious power-when the power used by a transmitter only depends on the distance to the receiver-as a mechanism for improving wireless capacity. We prove optimal bounds for inductive independence, implying a number of algorithmic applications. An algorithm is provided that achieves capacity that is-due to existing lower bounds-asymptotically best possible using oblivious power assignments. Improved approximation algorithms are provided for a number of problems involving both oblivious power and arbitrary power control, including connectivity, secondary spectrum auctions, and dynamic packet scheduling. We also show that the price of oblivious power-the relative increase in capacity possible when using unconstrained power control-is only doubly logarithmic in the maximum link length. [ABSTRACT FROM AUTHOR]

We consider the following single-machine scheduling problem, which is often denoted 1||∑ fj: we are given n jobs to be scheduled on a single machine, where each job j has an integral processing time pj, and there is a nondecreasing, nonnegative cost function fj (Cj) that specifies the cost of finishing j at time Cj; the objective is to minimize ∑j=1n fj (Cj). Bansal and Pruhs recently gave the first constant approximation algorithm with a performance guarantee of 16. We improve on this result by giving a primal-dual pseudo-polynomial-time algorithm based on the recently introduced knapsack-cover inequalities. The algorithm finds a schedule of cost at most four times the constructed dual solution. Although we show that this bound is tight for our algorithm, we leave open the question of whether the integrality gap of the linear program is less than 4. Finally, we show how the technique can be adapted to yield, for any ∈ > 0, a polynomial time (4 + ∈)-approximation algorithm for this problem. [ABSTRACT FROM AUTHOR]

Finding the length of the longest increasing subsequence (LIS) is a classic algorithmic problem. Let n denote the size of the array. Simple O(n log n) algorithms are known for this problem. We develop a polylogarithmic time randomized algorithm that for any constant δ>0, estimates the length of the LIS of an array to within an additive error of n. More precisely, the running time of the algorithm is(log n)c(1/δ)O(1/δ), where the exponent c is independent of δ. Previously, the best known polylogarithmic time algorithms could only achieve an additive n/2 approximation. With a suitable choice of parameters, our algorithm also gives, for any fixed т> 0, a multiplicative (1+т)-approximation to the distance to monotonicity εf (the fraction of entries not in the LIS), whose running time is polynomial in log(n) and 1/εf . The best previously known algorithm could only guarantee an approximation within a factor (arbitrarily close to) 2. [ABSTRACT FROM AUTHOR]

Linear programming (LP) has played a key role in the study of algorithms for combinatorial optimization problems. In the field of approximation algorithms, this is well illustrated by the uncapacitated facility location problem. A variety of algorithmic methodologies, such as LP-rounding and the primal-dual method, have been applied to and evolved from algorithms for this problem. Unfortunately, this collection of powerful algorithmic techniques had not yet been applicable to the more general capacitated facility location problem. In fact, all of the known algorithms with good performance guarantees were based on a single technique, local search, and no LP relaxation was known to efficiently approximate the problem. In this paper, we present an LP relaxation with a constant integrality gap for the capacitated facility location. We demonstrate that the fundamental theories of multicommodity flows and matchings provide key insights that lead to the strong relaxation. Our algorithmic proof of integrality gap is obtained by finally accessing the rich toolbox of LP-based methodologies: we present a constant factor approximation algorithm based on LP-rounding. [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]

We offer a novel classification of voting methods popular in social choice theory. Our classification is based on the more general problem of rank aggregation in which, beyond electing a winner, we also seek to compute an aggregate ranking of all the candidates; moreover, our classification is offered from a computational perspective--based on whether or not the voting method generalizes to an aggregation algorithm guaranteed to produce solutions that are near optimal in minimizing the distance of the aggregate ranking to the voters' rankings with respect to one of three well-known distance measures: the Kendall tau, the Spearman footrule, and the Spearman rho measures. We show that methods based on the average rank of the candidates (Borda counting), on the median rank of the candidates, and on the number of pairwise-majority wins (Copeland) all satisfy the near-optimality criterion with respect to each of these distance measures. On the other hand, we show that natural extensions of each of plurality voting, single transferable voting, and Simpson-Kramer minmax voting do not satisfy the near-optimality criterion with respect to these distance measures. [ABSTRACT FROM AUTHOR]