Search

We consider connectivity problems with orientation constraints. Given a directed graph D and a collection of ordered node pairs P let P[D] = {(u, v) ∈ P : D contains a uv-path}. In the Steiner Forest Orientation problem we are given an undirected graph G = (V, E) with edge-costs and a set P ⊆ V x V of ordered node pairs. The goal is to find a minimum-cost subgraph H of G and an orientation D of H such that P[D] = P. We give a 4-approximation algorithm for this problem. In the Maximum Pairs Orientation problem we are given a graph G and a multicollection of ordered node pairs P on V. The goal is to find an orientation D of G such that |P[D]| is maximum. Generalizing the result of Arkin and Hassin [Discrete Appl. Math., 116 (2002), pp. 271-278] for |P| = 2, we will show that for a mixed graph G (that may have both directed and undirected edges), one can decide in nO(|P|) time whether G has an orientation D with P[D] = P. (For undirected graphs this problem admits a polynomial time algorithm for any P, but it is NP-complete on mixed graphs.) For undirected graphs, we will show that one can decide whether G admits an orientation D with |P[D]| ≥ k in O(n + m) + 2O(k · log log k) time; hence this decision problem is fixed-parameter tractable, which answers an open question from Dorn et al. [Algorithms Molecular Biol., 6 (2011)]. We also show that Maximum Pairs Orientation admits ratio O(log |P|/ log log |P|), which is better than the ratio O(log n/ log log n) of Gamzu, Segev, and Sharan [Proceedings of WABI 2010, pp. 215-225] when |P| < n. [ABSTRACT FROM AUTHOR]

Given nf sites, each equipped with one facility, and nc cities, fault tolerant facility location (FTFL) [K. Jain and V. V. Vazirani, APPROX '00: Proceedings of the Third International Workshop on Approximation Algorithms for Combinatorial Optimization, Spinger, New York, 2000, pp. 177-183] requires computing a minimum-cost connection scheme such that each city connects to a specified number of facilities. When each city connects to exactly one facility, FTFL becomes the classical uncapacitated facility location problem (UFL) that is well-known NP hard. The current best solution to FTFL admits an approximation ratio 1.7245 due to Byrka, Srinivasan, and Swamy applying the dependent rounding technique announced recently [Proceedings of IPCO, 2010, pp. 244-257], which improves the ratio 2.076 obtained by Swamy and Shmoys based on LP rounding [ACM Trans. Algorithms, 4 (2008), pp. 1-27]. In this paper, we study a variant of the FTFL problem, namely, fault tolerant facility allocation (FTFA), as another generalization of UFL by allowing each site to hold multiple facilities and show that we can obtain better solutions for this problem. We first give two algorithms with 1.81 and 1.61 approximation ratios in time complexity O(m R log m) and O(Rn³), respectively, where R is the maximum number of facilities required by any city, m = nfnc, and n = max{nf, nc}. Instead of applying the dual-fitting technique that reduces the dual problem's solution to fit the original problem as used in the literature [K. Jain et al., Journal of the ACM, 50 (2003), pp. 795-824; K. Jain, M. Mahdian, and A. Saberi, STOC'02: Proceedings of the 34th Annual ACM Symposium on the Theory of Computing, New York, 2002, pp. 731-740; A. Saberi et al., Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques, Springer, New York, 2001, pp. 127-137], we propose a method called inverse dual-fitting that alters the original problem to fit the dual solution and show that this method is more effective for obtaining solutions of multifactor approximation. We show that applying inverse dual-fitting and factor-revealing techniques our second algorithm is also (1.11,1.78)- and (1,2)-approximation simultaneously. These results can be further used to achieve solutions of 1.52-approximation to FTFA and 4-approximation to the fault tolerant k-facility allocation problem in which the total number of facilities is bounded by k. These are currently the best bifactor and single-factor approximation ratios for the problems concerned. [ABSTRACT FROM AUTHOR]

In the minimum-cost k-(S,T) connected digraph (abbreviated as k-(S,T) connectivity) problem we are given a positive integer k, a directed graph G = (V, E) with nonnegative costs on the edges, and two subsets S, T of V; the goal is to find a subset of edges Ê of minimum cost such that the subgraph (V, Ê) has k edge-disjoint directed paths from each vertex in S to each vertex in T. Most of our results focus on a specialized version of the problem that we call the standard version, where every edge of positive cost has its tail in S and its head in T. This version of the problem captures NP-hard problems such as the minimum-cost k-vertex connected spanning subgraph problem. We give an approximation algorithm with a guarantee of O((logk)(logn)) for the standard version of the k-(S,T) connectivity problem, where n denotes the number of vertices. For k = 1, we give a simple 2-approximation algorithm that generalizes a well-known 2-approximation algorithm for the minimum-cost strongly connected spanning subgraph problem. For k = 2, we give a 3-approximation algorithm; this matches the best approximation guarantee known for the special case of the minimum-cost 2-vertex connected spanning subgraph problem. Besides the standard version, we study another version that is intermediate between the standard version and the problem in its full generality. In the relaxed version of the (S, T) connectivity problem, each edge of positive cost has its head in T but there is no restriction on the tail. We study the relaxed version with the connectivity parameter k fixed at one and observe that this version is at least as hard to approximate as the directed Steiner tree problem. We match this by giving an algorithm that achieves an approximation guarantee of α(n) +1 for the relaxed (S, T) connectivity problem, where α(n) denotes the best approximation guarantee available for the directed Steiner tree problem. The key to the analysis is a structural result that decomposes any feasible solution into a set of so-called junction trees that are disjoint on the vertices of T. Our algorithm and analysis specialize to the case when the input digraph is acyclic on T, meaning that there exists no dicycle that contains two distinct vertices of T. In this setting, we show that the relaxed (S, T) connectivity problem is at least as hard to approximate as the set covering problem, and we prove that our algorithm achieves a matching approximation guarantee of O(log |S|). [ABSTRACT FROM AUTHOR]

Given a directed simple graph G = (V, E) and a cost function c : E → R+, the power of a vertex u in a directed spanning subgraph H is given by pH(u) = maxuv∈E(H) c(uv), and corresponds to the energy consumption required for wireless node u to transmit to all nodes v with uv ∈ E(H). The power of H is given by p(H) = ∑u∈V pH(u)- Power Assignment seeks to minimize p(H) while H satisfies some connectivity constraint. In this paper, we assume E is bidirected (for every directed edge e ∈ E, the opposite edge exists and has the same cost), while H is required to be strongly connected. This is the original power assignment problem introduced by Chen and Huang in 1989, who proved that a bidirected minimum spanning tree has approximation ratio at most 2 (this is tight). In 2010, we introduced a greedy approximation algorithm and claimed a ratio of 1.992. Here we improve the algorithm's analysis to 1.85, combining techniques from Robins and Zelikovsky in 2000 for Steiner Tree, and Caragiannis, Flammini, and Moscardelli in 2007 for the broadcast version of Power Assignment, together with a simple idea inspired by Byrka and coworkers in 2010. The proof also shows that a natural linear programming relaxation, introduced by Calinescu and Qiao in 2012, has integrality gap at most 1.85. [ABSTRACT FROM AUTHOR]

We investigate the computational difficulty of approximating the partition function of the ferromagnetic Ising model on a regular matroid. Jerrum and Sinclair have shown that there is a fully polynomial randomized approximation scheme (FPRAS) for the class of graphic matroids. On the other hand, the authors have previously shown, subject to a complexity-theoretic assumption, that there is no FPRAS for the class of binary matroids, which is a proper superset of the class of graphic matroids. In order to map out the region where approximation is feasible, we focus on the class of regular matroids, an important class of matroids which properly includes the class of graphic matroids and is properly included in the class of binary matroids. Using Seymour's decomposition theorem, we give an FPRAS for the class of regular matroids. [ABSTRACT FROM AUTHOR]

We give deterministic Õ(22n)-time Õ(2n)-space algorithms to solve all the most important computational problems on point lattices in NP, including the shortest vector problem (SVP), closest vector problem (CVP), and shortest independent vectors problem (SIVP). This improves the nO(n) running time of the best previously known algorithms for CVP [R. Kannan, Math. Oper. Res., 12 (1987), pp. 415-440] and SIVP [D. Micciancio, Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms, 2008, pp. 84-93] and gives a deterministic and asymptotically faster alternative to the 2O(n)-time (and space) randomized algorithm for SVP of Ajtai, Kumar, and Sivakumar [Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, 2001, pp. 266-275]. The core of our algorithm is a new method to solve the closest vector problem with preprocessing (CVPP) that uses the Voronoi cell of the lattice (described as intersection of half-spaces) as the result of the preprocessing function. A direct consequence of our results is a derandomization of the best current polynomial time approximation algorithms for SVP and CVP, achieving a 2O(n log log n/ log n) approximation factor. [ABSTRACT FROM AUTHOR]

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

This paper presents near-optimal guarantees for stable and robust image recovery from undersam-pled noisy measurements using total variation minimization. In particular, we show that from O(s log (N)) nonadaptive linear measurements, an image can be reconstructed to within the best s-term approximation of its gradient up to a logarithmic factor, and this factor can be removed by taking slightly more measurements. Along the way, we prove a strengthened Sobolev inequality for functions lying in the null space of a suitably incoherent matrix. [ABSTRACT FROM AUTHOR]

In this paper we prove new properties of hypergraphic linear programming relaxations for the Steiner tree problem. In particular, we show that a partition-based relaxation has the same value as other relaxations based on subtours and directed cuts. Additionally, we establish structural properties of basic solutions by using uncrossing methods. For quasi-bipartite instances we show that these hypergraphic relaxations have the same value as the well-studied graphic bidirected cut relaxation. We show how to analyze several approximation algorithms relative to the hypergraphic linear programs; one gives an approximation ratio and integrality gap of at most √3 ≃ 1.729 for the Steiner tree problem when the full components arrive online. [ABSTRACT FROM AUTHOR]

We study the approximate nearest neighbor problem for metric spaces where the query points are constrained to lie on a subspace of low doubling dimension, while the data is high dimensional. We show that this problem can be solved efficiently despite the high dimensionality of the data. [ABSTRACT FROM AUTHOR]

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

We study the design of local algorithms for massive graphs. A local graph algorithm is one that finds a solution containing or near a given vertex without looking at the whole graph. We present a local clustering algorithm. Our algorithm finds a good cluster--a subset of vertices whose internal connections are significantly richer than its external connections--near a given vertex. The running time of our algorithm, when it finds a nonempty local cluster, is nearly linear in the size of the cluster it outputs. The running time of our algorithm also depends polylogarithmically on the size of the graph and polynomially on the conductance of the cluster it produces. Our clustering algorithm could be a useful primitive for handling massive graphs, such as social networks and web-graphs. As an application of this clustering algorithm, we present a partitioning algorithm that finds an approximate sparsest cut with nearly optimal balance. Our algorithm takes time nearly linear in the number edges of the graph. Using the partitioning algorithm of this paper, we have designed a nearly linear time algorithm for constructing spectral sparsifiers of graphs, which we in turn use in a nearly linear time algorithm for solving linear systems in symmetric, diagonally dominant matrices. The linear system solver also leads to a nearly linear time algorithm for approximating the second-smallest eigenvalue and corresponding eigenvector of the Laplacian matrix of a graph. These other results are presented in two companion papers. [ABSTRACT FROM AUTHOR]

Given a directed graph G = (V, E) and an integer k ≥ 1, a k-transitive-closure-spanner (k-TC-spanner) of G is a directed graph H = (V, EH) that has (1) the same transitive-closure as G and (2) diameter at most k. These spanners were implicitly studied in the context of circuit complexity, data structures, property testing, and access control, and properties of these spanners have been rediscovered over the span of 20 years. We abstract the common task implicitly tackled in these diverse applications as the problem of constructing sparse TC-spanners. We initiate the study of approximability of the size of the sparsest k-TC-spanner of a given directed graph. We completely resolve the approximability of 2-TC-spanners, showing that it is Θ(log n) unless P = NP. For k > 2, we present a polynomial time algorithm that finds a k-TC-spanner with size within O((n log n)1-1/k) of the optimum. Our techniques also yield algorithms with the first nontrivial approximation ratio for well-studied problems on directed spanners when k > 3: DIRECTED k-SPANNER, CLIENT/SERVER DIRECTED k-SPANNER, and k-DIAMETER SPANNING SUBGRAPH. For constant k ≥ 3, we show that the size of the sparsest k-TC-spanner is hard to approximate within a factor of 2log1-∈ n for any ε ∈ (0, 1) unless NP ⊆ DTIME(npolylog n). Finally, we study the size of the sparsest k-TC-spanners for H-minor-free graph families. Combining our constructions with our insight that 2-TC-spanners can be used for designing property testers, we obtain a monotonicity tester with O(log² n/ε) queries for any poset whose transitive reduction, when viewed as an undirected graph, is free of a fixed minor. Previously, the best upper bound on the query complexity for such graphs was O(√n/ε). [ABSTRACT FROM AUTHOR]

Consider the edge-connectivity survivable network design problem (SNDP): given a graph G = (V, E) with edge-costs, and edge-connectivity requirements rij ∈ Z≥0 for every pair of vertices i, j ∈ V, find an (approximately) minimum-cost network that provides the required connectivity. While this problem is known to admit good approximation algorithms in the offline case, no algorithms were known for this problem in the online setting. In this paper, we give a randomized Õ(rmax log³ n)-competitive online algorithm for this edge-connectivity network design problem that runs in time O(mrmax ), where rmax = maxij rij. Our algorithms use the standard embeddings of graphs into random subtrees (i.e., into singly connected subgraphs) as an intermediate step to get algorithms for higher connectivity. As a consequence of using these random embeddings, our algorithms are competitive only against oblivious adversaries. Our results for the online problem give us approximation algorithms that admit strict cost-shares with the same strictness value. This, in turn, implies approximation algorithms for (a) the rent-or-buy version and (b) the (two-stage) stochastic version of the edge-connected network design problem with independent arrivals. If we are in the case when the underlying graph is complete and the edge-costs are metric (i.e., the triangle inequality is satisfied), we improve on our results to give an O(log n)-competitive deterministic online algorithm for the rooted version of the problem, and constant-factor approximation algorithms for the rent-or-buy and stochastic variants of SNDP. [ABSTRACT FROM AUTHOR]

We show how to compute the edit distance between two strings of length n up to a factor of 2Õ(√log n) in n1+o (1) time. This is the first subpolynomial approximation algorithm for this problem that runs in near-linear time, improving on the state-of-the-art n1/3+o(1) approximation. Previously, approximation of 2Õ (√log n) was known only for embedding edit distance into l1, and it is not known if that embedding can be computed in less than quadratic time. [ABSTRACT FROM AUTHOR]

The need to compute small con-eigenvalues and the associated con-eigenvectors of positive-definite Cauchy matrices naturally arises when constructing rational approximations with a (near) optimally small L∞ error. Specifically, given a rational function with n poles in the unit disk, a rational approximation with m << n poles in the unit disk may be obtained from the mth con-eigenvector of an n x n Cauchy matrix, where the associated con-eigenvalue λm > 0 gives the approximation error in the L∞ norm. Unfortunately, standard algorithms do not accurately compute small con-eigenvalues (and the associated con-eigenvectors) and, in particular, yield few or no correct digits for con-eigenvalues smaller than the machine roundoff. We develop a fast and accurate algorithm for computing con-eigenvalues and con-eigenvectors of positive-definite Cauchy matrices, yielding even the tiniest con-eigenvalues with high relative accuracy. The algorithm computes the mth con-eigenvalue in O(m²n) operations and, since the con-eigenvalues of positive-definite Cauchy matrices decay exponentially fast, we obtain (near) optimal rational approximations in O(n (log δ-1)²) operations, where δ is the approximation error in the L∞ norm. We provide error bounds demonstrating high relative accuracy of the computed con-eigenvalues and the high accuracy of the unit con-eigenvectors. We also provide examples of using the algorithm to compute (near) optimal rational approximations of functions with singularities and sharp transitions, where approximation errors close to machine roundoff are obtained. Finally, we present numerical tests on random (complex-valued) Cauchy matrices to show that the algorithm computes all the con-eigenvalues and con-eigenvectors with nearly full precision. [ABSTRACT FROM AUTHOR]

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

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

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

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

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

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]

Since the celebrated work of Jerrum, Sinclair, and Vigoda [J. ACM, 51 (2004), pp. 671--697], we have known that the permanent of a matrix with entries in {0, 1} can be approximated in randomized polynomial time by using a rapidly mixing Markov chain to sample perfect matchings of a bipartite graph. A separate strand of the literature has pursued the possibility of an alternate, algebraic polynomial-time approximation scheme. These schemes work by replacing each 1 with a random element of an algebra A and considering the determinant of the resulting matrix. In the case where A is noncommutative, this determinant can be defined in several ways. We show that for some estimators based on the conventional determinant, the critical ratio of the second moment to the square of the first--and therefore the number of trials we need to obtain a good estimate of the permanent--is (1 + O(1/d))n when A is the algebra of d X d matrices. These results can be extended to group algebras and semisimple algebras in general. We also study the symmetrized determinant of Barvinok, showing that the resulting estimator has small variance when d is large enough. However, if d is constant--the only case in which an efficient algorithm is known--we show that the critical ratio exceeds 2n/nO(d). Thus our results do not provide a new polynomial-time approximation scheme for the permanent. Indeed, they suggest that the algebraic approach to approximating the permanent faces significant obstacles. We obtain these results using diagrammatic techniques in which we express matrix products as contractions of tensor products. When these matrices are chosen randomly according to the Gaussian distribution, we can evaluate the trace of these products in terms of the cycle structure of a suitably random permutation. In the symmetrized case, our estimates are then derived by a connection with the character theory of the symmetric group. [ABSTRACT FROM AUTHOR]

We present the best known algorithms for approximating the minimum-size undirected k-edge connected spanning subgraph. For simple graphs our approximation ratio is 1 + 1/(2k) + O(1/k²). The more precise version of this bound requires k ≥7, and for all such k it improves the long-standing performance ratio of Cheriyan and Thurimella [SIAM J. Comput., 30 (2000), pp. 528-560], 1 + 2/(k + 1). The improvement comes in two steps. First we show that for simple k-edge connected graphs, any laminar family of degree k sets is smaller than the general bound (n(1 + 3/k + O(1/k√k)) versus 2n). This immediately implies that iterated rounding improves the performance ratio of Cheriyan and Thurimella. The second step carefully chooses good edges for rounding. For multigraphs our approximation ratio is 1+(21/11)k < 1+1.91/k for any k > 1. This improves the previous ratio 1+2/k [H. N. Gabow, M. X. Goemans, E. Tardos, and D. P. Williamson, Networks, 53 (2009), pp. 345-357]. It is of interest since it is known that for some constant c >0, an approximation ratio ≤ 1+c/k implies P = NP. Our approximation ratio extends to the minimumsize Steiner network problem, where k denotes the average vertex demand. The algorithm exploits rounding properties of the first two linear programs in iterated rounding. [ABSTRACT FROM AUTHOR]

We construct a small set of explicit linear transformations mapping ℝn to ℝt, where t = O(log(γ-1)ε-2), such that the L2 norm of any vector in ℝn is distorted by at most 1 ± ε in at least a fraction of 1-γ of the transformations in the set. Albeit the tradeoff between the size of the set and the success probability is suboptimal compared with probabilistic arguments, we nevertheless are able to apply our construction to a number of problems. In particular, we use it to construct an ε-sample (or pseudorandom generator) for linear threshold functions on 픔n-1 for ε = o(1). We also use it to construct an ε-sample for spherical digons in 픔n-1 for ε = o(1). This construction leads to an efficient oblivious derandomization of the Goemans-Williamson Max-Cut algorithm and similar approximation algorithms (i.e., we construct a small set of hyperplanes such that for any instance we can choose one of them to generate a good solution). Our technique for constructing an ε-sample for linear threshold functions on the sphere is considerably different than previous techniques that rely on k-wise independent sample spaces. [ABSTRACT FROM AUTHOR]

New algorithms are proposed for the Tucker approximation of a 3-tensor accessed only through a tensor-by-vector-by-vector multiplication subroutine. In the matrix case, the Krylov methods are methods of choice to approximate the dominant column and row subspaces of a sparse or structured matrix given through a matrix-by-vector operation. Using the Wedderburn rank reduction formula, we propose a matrix approximation algorithm that computes the Krylov subspaces and can be generalized to 3-tensors. The numerical experiments show that on quantum chemistry data the proposed tensor methods outperform the minimal Krylov recursion of Savas and Eldén. [ABSTRACT FROM AUTHOR]

We present a general class of compressed sensing matrices which are then demonstrated to have associated sublinear-time sparse approximation algorithms. We then develop methods for constructing specialized matrices from this class which are sparse when multiplied with a discrete Fourier transform matrix. Ultimately, these considerations improve previous sampling requirements for deterministic sparse Fourier transform methods. [ABSTRACT FROM AUTHOR]

We present a bundle method for convex nondifferentiable minimization where the model is a piecewise-quadratic convex approximation of the objective function. Unlike standard bundle approaches, the model only needs to support the objective function from below at a properly chosen (small) subset of points, as opposed to everywhere. We provide the convergence analysis for the algorithm, with a general form of master problem which combines features of trust region stabilization and proximity stabilization, taking care of all the important practical aspects such as proper handling of the proximity parameters and the bundle of information. Numerical results are also reported. [ABSTRACT FROM AUTHOR]

We introduce the notion of a canonical tester for a class of properties on distributions, that is, a tester strong and general enough that "a distribution property in the class is testable if and only if the canonical tester tests it." We construct a canonical tester for the class of properties of one or two distributions that are symmetric and satisfy a certain weak continuity condition. Analyzing the performance of the canonical tester on specific properties resolves two open problems, establishing lower bounds that match known upper bounds: we show that distinguishing between entropy < α or > β on distributions over nα/β-o(1) samples, and distinguishing whether a pair of distributions has statistical distance < α or > β requires n 1-o(1) samples. Our techniques also resolve a conjecture about a property that our canonical tester does not apply to: distinguishing identical distributions from those with statistical distance > ½ requires ω(n2/3 ) samples. [ABSTRACT FROM AUTHOR]

We introduce several generalizations of classical computer science problems obtained by replacing simpler objective functions with general submodular functions. The new problems include submodular load balancing, which generalizes load balancing or minimum-make span scheduling, submodular sparsest cut and submodular balanced cut, which generalize their respective graph cut problems, as well as submodular function minimization with a cardinality lower bound. We establish upper and lower bounds for the approximability of these problems with a polynomial number of queries to a function-value oracle. The approximation guarantees that most of our algorithms achieve are of the order of √n/ln n. We show that this is the inherent difficulty of the problems by proving matching lower bounds. We also give an improved lower bound for the problem f approximating a monotone submodular function everywhere. In addition, we present an algorithm for approximating submodular functions with a special structure, whose guarantee is close to the lower bound. Although quite restrictive, the class of functions with this structure includes the ones that are used for lower bounds both by us and in previous work. [ABSTRACT FROM AUTHOR]

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

We investigate nonparametric multiproduct pricing problems, in which we want to find revenue maximizing prices for products P based on a set of customer samples C. We mostly focus on the unit-demand case, in which products constitute strict substitutes and each customer aims to purchase a single product. In this setting a customer sample consists of a number of nonzero values for different products and possibly an additional product ranking. Once prices are fixed, each customer chooses to buy one of the products she can afford based on some predefined selection rule. We distinguish between the min-buying, max-buying, and rank-buying models. Some of our results also extend to single-minded pricing, in which case products are strict complements and every customer seeks to buy a single set of products, which she purchases if the sum of prices is below her valuation for that set. For the min-buying model we show that the revenue maximization problem is not approximable within factor O (logepsilon|C|) for some constant ∈ > 0, unless NP ⊆DTIME(nO(log log n)), thereby almost closing the gap between the known algorithmic results and previous lower bounds. We also prove in approximability within O(l∈), being an upper bound on the number of nonzero values per customer, and O(|P|∈) under slightly stronger assumptions and provide matching upper bounds. Surprisingly, these hardness results hold even if a price ladder constraint, i.e., a predefined order on the prices of all products, is given. Without the price ladder constraint we obtain similar hardness results for the special case of uniform valuations, i.e., the case that every customer has identical values for all the products she is interested in, assuming specific hardness of the balanced bipartite independent set problem in constant degree graphs or hardness of refuting random 3CNF formulas. Introducing a slightly more general problem definition in which customers are given as an explicit probability distribution, we obtain inapproximability within O(|P|∈) assuming NP ⊈ ∩δ>0 BPTIME Due to image rights restrictions, multiple line equation(s) cannot be graphically displayed.. These results apply to single-minded pricing as well. For the max-buying model a polynomial-time approximation scheme exists if a price ladder is given. We give a matching lower bound by proving strong NP-hardness. Assuming limited product supply, we analyze a generic local search algorithm and prove that it is 2-approximate. Finally, we discuss implications for the rank-buying model. [ABSTRACT FROM AUTHOR]

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

Given dissimilarity data on pairs of objects in a set, we study the problem of fitting a tree metric to this data so as to minimize additive error (i.e., some measure of the difference between the tree metric and the given data). This problem arises in constructing an M-level hierarchical clustering of objects (or an ultrametric on objects) so as to match the given dissimilarity data--a basic problem in statistics. Viewed in this way, the problem is a generalization of the correlation clustering problem (which corresponds to M = 1). We give a very simple randomized combinatorial algorithm for the M-level hierarchical clustering problem that achieves all approximation ratio of M + 2. This is a generalization of a previous factor 3 algorithm for correlation clustering on complete graphs. The problem of fitting tree metrics also arises in phylogeny where the objective is to learn the evolution tree by fitting a tree to dissimilarity data on taxa. The quality of the fit is measured by taking the lp norm of the difference between the tree metric constructed and the given data. Previous results obtained a factor 3 approximation for finding the closest tree metric under the l ∞ norm. No nontrivial approximation for general lp norms was known before. We present a novel linear program formulation for this problem and obtain an O((log n log log n)1/p)-approximation to the closest ultrametric under the lp norm using this. Our techniques are based on representing and viewing an ultrametric as a hierarchy of clusterings and may be useful in other contexts. [ABSTRACT FROM AUTHOR]

We study the maximum weight matching problem in the semi-streaming model, and improve on the currently best one-pass algorithm due to Zelke [Proceedings of the 25th Annual Symposium on Theoretical Aspects of Computer Science, 2008, pp. 669-680] by devising a deterministic approach whose performance guarantee is 4.91 + ε. In addition, we study preemptive online algorithms, a class of algorithms related to one-pass semi-streaming algorithms, where we are allowed to maintain only a feasible matching in memory at any point in time. We provide a lower bound of 4.967 on the competitive ratio of any such deterministic algorithm, and hence show that future improvements will have to store in memory a set of edges that is not necessarily a feasible matching. We conclude by presenting an empirical study, conducted in order to compare the practical performance of our approach to that of previously suggested algorithms. [ABSTRACT FROM AUTHOR]

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

Low-rank matrix approximations, such as the truncated singular value decomposition and the rank-revealing QR decomposition, play a central role in data analysis and scientific computing. This work surveys and extends recent research which demonstrates that randomization offers a powerful tool for performing low-rank matrix approximation. These techniques exploit modern computational architectures more fully than classical methods and open the possibility of dealing with truly massive data sets. This paper presents a modular framework for constructing randomized algorithms that compute partial matrix decompositions. These methods use random sampling to identify a subspace that captures most of the action of a matrix. The input matrix is then compressed--either explicitly or implicitly--to this subspace, and the reduced matrix is manipulated deterministically to obtain the desired low-rank factorization. In many cases, this approach beats its classical competitors in terms of accuracy, robustness, and/or speed. These claims are supported by extensive numerical experiments and a detailed error analysis. The specific benefits of randomized techniques depend on the computational environment. Consider the model problem of finding the k dominant components of the singular value decomposition of an m x n matrix, (i) For a dense input matrix, randomized algorithms require O(mn log (k)) floating-point operations (flops) in contrast to O(mnk) for classical algorithms, (ii) For a sparse input matrix, the flop count matches classical Krylov subspace methods, but the randomized approach is more robust and can easily be reorganized to exploit multiprocessor architectures, (iii) For a matrix that is too large to fit in fast memory, the randomized techniques require only a constant number of passes over the data, as opposed to O(k) passes for classical algorithms. In fact, it is sometimes possible to perform matrix approximation with a single pass over the data. [ABSTRACT FROM AUTHOR]

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

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

We study the partial capacitated vertex cover problem (PCVC) in which the input consists of a graph G and a covering requirement L. Each edge e in G is associated with a demand (or load) l(e), and each vertex v is associated with a (soft) capacity c(v) and a weight w(v). A feasible solution is an assignment of edges to vertices such that the total demand of assigned edges is at least L. The weight of a solution is ∑V α(v)w(v), where α(v) is the number of copies of v required to cover the demand of the edges that are assigned to v. The goal is to find a solution of minimum weight. We consider three variants of PCVC. In PCVC with separable demands the only requirement is that the total demand of edges assigned to v is at most α(v)c(v). In PCVC with inseparable demands there is an additional requirement that if an edge is assigned to v, then it must be assigned to one of its copies. The third variant is the unit demands version. We present 3-approximation algorithms for both PCVC with separable demands and PCVC with inseparable demands. We also present a 2-approximation algorithm for PCVC with unit demands. We show that similar results can be obtained for PCVC in hypergraphs and for the prize collecting version of capacitated vertex cover. Our algorithms are based on a unified approach for designing and analyzing approximation algorithms for capacitated covering problems. This approach yields simple algorithms whose analyses rely on the local ratio technique and sophisticated charging schemes. [ABSTRACT FROM AUTHOR]

Only recently Goyal, Olver, and Shepherd [PToc. STOC, ACM, New York, 2008] proved that the symmetric virtual private network design (sVPN) problem has the tree routing property, namely, that there always exists all optimal solution to the problem whose support is a tree. Combining this with previous results by Fingerhut, Suri, and Turner [J. Algorithms. 24 (1997), pp. 287-309] and Gupta et al. [Proc. STOC, ACM, New York, 2001], sVPN can be solved in polynomial time. In this paper we investigate an APX-hard generalization of sVPn, where the contribution of each edge to the total cost is proportional to some non-negative, concave, and nondecreasing function of the capacity reservation. We show that the tree routing property extends to the new problem and give a constant-factor approximation algorithm for it. We also show that the undirected uncapacitated single-source minimum concave-cost flow problem has the tree routing property when the cost function has some property of symmetry. [ABSTRACT FROM AUTHOR]

We consider the vanishing viscosity approximation of the traffic model, proposed by Lighthill, Whitham, and Richards, on a network composed by a single junction with n incoming and m outgoing roads. We prove that a solution of the parabolic approximation exists and, as the viscosity vanishes, the solution of the parabolic problem converges to a solution of the original problem. [ABSTRACT FROM AUTHOR]

Multicommodity facility location refers to the extension of facility location to allow for different clients' demands for different goods from among a finite set of goods. This leads to several optimization problems, depending on the cost of opening a facility (now a function of the commodities it serves). In this paper, we introduce and provide approximation algorithms for two fairly general versions of multicommodity facility location. We formulate integer programming models for these problems, and use them to provide approximation algorithms for the problems that are close to the inapproximability thresholds. [ABSTRACT FROM AUTHOR]

We present an efficient polynomial time approximation scheme (EPTAS) for scheduling on uniform processors, i.e., finding a minimum length schedule for a set of n independent jobs on m processors with different speeds (a fundamental NP-hard scheduling problem). The previous best polynomial time approximation scheme (PTAS) by Hochbaum and Shmoys has a running time of (n/ϵ)O(1/ϵ2). Our algorithm, based on a new mixed integer linear program (MILP) formulation with a constant number of integral variables and an interesting rounding method, finds a schedule whose length is within a relative error ϵ of the optimum and has a running time of 2O(1/ϵ2 log(1/ϵ)3)+poly(n). [ABSTRACT FROM AUTHOR]

We present a simple scheme extending the shallow partitioning data structures of Matoušek, which supports efficient approximate halfspace range-counting queries in ℝd with relative error e. Specifically, the problem is, given a set P of n points in #x211D;d, to preprocess them into a data structure that returns, for a query halfspace h, a number t so that (1-ϵ)|h∩P| ≤ t ≤ (1+ϵ)|h∩P|. One of our data structures requires linear storage and O(n1+δ) preprocessing time, for any δ > 0, and answers a query in time O(δ-γn1-1/⌊d/2⌋2b log* n) for any γ > 2/⌊d/2⌋; the choice of γ and δ affects b and the implied constants. Several variants and extensions are also discussed. As presented, the construction of the structure is mostly deterministic, except for one critical randomized step, and so are the query, storage, and preprocessing costs. The quality of approximation, for every query, is guaranteed with high probability. The construction can also be fully derandomized, at the expense of increasing preprocessing time. [ABSTRACT FROM AUTHOR]

We consider one-round games between a classical verifier and two provers who share entanglement. We show that when the constraints enforced by the verifier are "unique" constraints (i.e., permutations), the value of the game can be well approximated by a semidefinite program (SDP). Essentially the only algorithm known previously was for the special case of binary answers, as follows from the work of Tsirelson in 1980. Among other things, our result implies that the variant of the unique games conjecture where we allow the provers to share entanglement is false. Our proof is based on a novel "quantum rounding technique," showing how to take a solution to an SDP and transform it into a strategy for entangled provers. Using our approximation by an SDP, we also show a parallel repetition theorem for unique entangled games. [ABSTRACT FROM AUTHOR]

The (undirected) Steiner Network problem is as follows: given a graph G = (V,E) with edge/node-weights and edge-connectivity requirements {r(u, v) : u, v ∈ U ⊆ V }, find a minimum-weight subgraph H of G containing U so that the uv-edge-connectivity in H is at least r(u, v) for all u, v ∈ U. The seminal paper of Jain [Combinatorica, 21 (2001), pp. 39-60], and numerous papers preceding it, considered the Edge-Weighted Steiner Network problem, with weights on the edges only, and developed novel tools for approximating minimum-weight edge-covers of several types of set functions and families. However, for the Node-Weighted Steiner Network (NWSN) problem, nontrivial approximation algorithms were known only for 0, 1 requirements. We make an attempt to change this situation by giving the first nontrivial approximation algorithm for NWSN with arbitrary requirements. Our approximation ratio for NWSN is rmax·O(ln |U|), where rmax = maxu,v∈U r(u, v). This generalizes the result of Klein and Ravi [J. Algorithms, 19 (1995), pp. 104-115] for the case rmax = 1. We also give an O(ln |U|)-approximation algorithm for the node-connectivity variant of NWSN (when the paths are required to be internally disjoint) for the case rmax = 2. Our results are based on a much more general approximation algorithm for the problem of finding a minimum nodeweighted edge-cover of an uncrossable set-family. Finally, we give evidence that a polylogarithmic approximation ratio for NWSN with large rmax might not exist even for |U| = 2 and unit weights. [ABSTRACT FROM AUTHOR]

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