Search

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

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

Moss and Rabani study constrained node-weighted Steiner tree problems with two independent weight values associated with each node, namely, cost and prize (or penalty). They give an O(log n)-approximation algorithm for the node-weighted prize-collecting Steiner tree problem (PCST) where the goal is to minimize the cost of a tree plus the penalty of vertices not covered by the tree. They use the algorithm for PCST to obtain a bicriteria (2;O(log n))-approximation algorithm for the budgeted node-weighted Steiner tree problem where the goal is to maximize the prize of a tree with a given budget for its cost. Their solution may cost up to twice the budget, but collects a factor ( 1 log n ) of the optimal prize. We improve these results from at least two aspects. Our rst main result is a primal-dual O(log h)-approximation algorithm for a more general problem, node-weighted prize-collecting Steiner forest (PCSF), where we have h demands each requesting the connectivity of a pair of vertices. Our algorithm can be seen as a greedy algorithm which reduces the number of demands by choosing a structure with minimum cost-to-reduction ratio. This natural style of argument leads to a much simpler algorithm than that of Moss and Rabani for PCST. Our second main contribution is for the budgeted node-weighted Steiner tree problem, which is also an improvement to the work of Moss and Rabani. In the unrooted case, we improve upon an existing O(log2 n)-approximation by Guha et al., and present an O(log n)-approximation algorithm without any budget violation. For the rooted case, where a speci ed vertex has to appear in the solution tree, we improve the bicriteria result of Moss and Rabani to the bicriteria approximation ratio of (1 + ;O(log n)=2) for any positive (possibly subconstant) ∈. That is, for any permissible budget violation 1 + ∈, we present an algorithm achieving a trade o in the guarantee for the prize. Indeed, we show that this is almost tight for the natural linear-programming relaxation used by us as well as in the previous works. [ABSTRACT FROM AUTHOR]

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]

Recently it was shown how necessary and sufficient information for solving an orthogonally invariant linear approximation problem AX ≈ B with multiple right-hand sides can be revealed through the so-called core problem reduction; see [I. Hnětynková, M. Plešinger, and Z. Strakoš, SIAM J. Matrix Anal. Appl., 34 (2013), pp. 917-931]. The total least squares (TLS) serves as an important example of such approximation problem. Solvability of TLS was discussed in the full generality in [I. Hnětynková et al., SIAM J. Matrix Anal. Appl., 32 (2011), pp. 748-770]. This theoretical study investigates solvability of core problems with multiple right-hand sides in the TLS sense. It is shown that, contrary to the single right-hand side case, a core problem with multiple right-hand sides may not have a TLS solution. Further possible internal structure of core problems is studied. Outputs of the classical TLS algorithm for the original problem AX ≈ B and for the core problem within AX ≈ B are compared. [ABSTRACT FROM AUTHOR]

Given a capacitated graph G = (V, E) and a set of terminals K ⊆ V, how should we produce a graph H only on the terminals K so that every (multicommodity) flow between thw terminals in G could be supported in H with low congestion, and vice versa? (Such a graph H is called a flow sparsifier for G.) What if we want H to be a "simple" graph? What if we allow H to be a convex combination of simple graphs? Improving on results of Moitra [Proceedings of the 50th IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Los Alamitos, CA, 2009, pp. 3-12] and Leighton and Moitra [Proceedings of the 42nd ACM Symposium on Theory of Computing, ACM, New York, 2010, pp. 47-56], we give efficient algorithms for constructing (a) a flow sparsifier H that maintains congestion up to a factor of O(log κ/log log κ), where κ = | K |(b) a convex combination of trees over the terminals K that maintains congestion up to a factor of O(log k); (c) for a planar graph G, a convex combination of planar graphs that maintains congestion up to a constant factor. This requires us to give a new algorithm for the 0-extension problem, the first one in which the preimages of each terminal are connected in G. Moreover, this result extends to minor-closed families of graphs. Our bounds immediately imply improved approximation guarantees for several terminal-based cut and ordering problems. [ABSTRACT FROM AUTHOR]

We present a 6-approximation algorithm for the minimum-cost κ-node connected spanning subgraph problem, assuming that the number of nodes is at least κ³ (κ - 1) + κ. We apply a combinatorial preprocessing, based on the Frank--Tardos algorithm for κ-outconnectivity, to transform any input into an instance such that the iterative rounding method gives a 2-approximation guarantee. This is the first constant factor approximation algorithm even in the asymptotic setting of the problem, that is, the restriction to instances where the number of nodes is lower bounded by a function of κ. [ABSTRACT FROM AUTHOR]

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

The similarity of two polygonal curves can be measured using the Fréchet distance. We introduce the notion of a more robust Fréchet distance, where one is allowed to shortcut between vertices of one of the curves. This is a natural approach for handling noise, in particular batched outliers. We compute a (3 + ε)-approximation to the minimum Fréchet distance over all possible such shortcuts, in near linear time, if the curve is c-packed and the number of shortcuts is either small or unbounded. To facilitate the new algorithm we develop several new tools: (a) a data structure for preprocessing a curve (not necessarily c-packed) that supports (1 + ε)-approximate Fréchet distance queries between a subcurve (of the original curve) and a line segment; (b) a near linear time algorithm that computes a permutation of the vertices of a curve, such that any prefix of 2k - 1 vertices of this permutation forms an optimal approximation (up to a constant factor) to the original curve compared to any polygonal curve with k vertices, for any k > 0; and (c) a data structure for preprocessing a curve that supports approximate Fréchet distance queries between a subcurve and query polygonal curve. The query time depends quadratically on the complexity of the query curve and only (roughly) logarithmically on the complexity of the original curve. To our knowledge, these are the first data structures to support these kind of queries efficiently. [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 continue the recent line of work on the connection between semidefinite programming (SDP)-based approximation algorithms and the unique games conjecture. Given any Boolean 2-CSP (or, more generally, any Boolean 2-CSP with real-valued "predicates"), we show how to reduce the search for a good inapproximability result to a certain numeric minimization problem. Furthermore, we give an SDP-based approximation algorithm and show that the approximation ratio of this algorithm on a certain restricted type of instances is exactly the inapproximability ratio yielded by our hardness result. We conjecture that the restricted type required for the hardness result is in fact no restriction, which would imply that these upper and lower bounds match exactly. This conjecture is supported by all existing results for specific 2-CSPs. As an application, we show that Max 2-And is unique games-hard to approximate within 0.87435. This improves upon the best previous hardness of αGW + ϵ ≈ 0.87856 and comes very close to matching the approximation ratio of the best algorithm known, 0.87401. It also establishes that balanced instances of Max 2-And, i.e., instances in which each variable occurs positively and negatively equally often, are not the hardest to approximate, as these can be approximated within a factor αGW and that Max Cut is not the hardest 2-CSP. [ABSTRACT FROM AUTHOR]

In this paper we consider the following maximum budgeted allocation (MBA) problem: Given a set of m indivisible items and n agents, with each agent i willing to pay bij on item j and with a maximum budget of Bi, the goal is to allocate items to agents to maximize revenue. The problem naturally arises as auctioneer revenue maximization in budget-constrained auctions and as the winner determination problem in combinatorial auctions when utilities of agents are budgetedadditive. Our main results are as follows: (i) We give a 3/4-approximation algorithm for MBA improving upon the previous best of ≃ 0.632 [N. Andelman and Y. Mansour, Proceedings of the 9th Scandinavian Workshop on Algorithm Theory (SWAT), 2004, pp. 26-38], [J. Vondrák, Proceedings of the 40th Annual ACM Symposium on the Theory of Computing (STOC), 2008, pp. 67-74] (also implied by the result of [U. Feige and J. Vondrák, Proceedings of the 47th IEEE Symposium on Foundations of Computer Science (FOCS), 2006, pp. 667-676]). Our techniques are based on a natural LP relaxation of MBA, and our factor is optimal in the sense that it matches the integrality gap of the LP. (ii) We prove it is NP-hard to approximate MBA to any factor better than 15/16; previously only NP-hardness was known [T. Sandholm and S. Suri, Games Econom. Behav., 55 (2006), pp. 321-330], [B. Lehmann, D. Lehmann, and N. Nisan, Proceedings of the 3rd ACM Conference on Electronic Commerce (EC), 2001, pp. 18-28]. Our result also implies NP-hardness of approximating maximum submodular welfare with demand oracle to a factor better than 15/16, improving upon the best known hardness of 275/276 [U. Feige and J. Vondrák, Proceedings of the 47th IEEE Symposium on Foundations of Computer Science (FOCS), 2006, pp. 667-676]. (iii) Our hardness techniques can be modified to prove that it is NP-hard to approximate the generalized assignment problem (GAP) to any factor better than 10/11. This improves upon the 422/423 hardness of [C. Chekuri and S. Khanna, Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2000, pp. 213-222], [M. Chlebík and J. Chlebíková, Proceedings of the 8th Scandinavian Workshop on Algorithm Theory (SWAT), 2002, pp. 170-179]. We use iterative rounding on a natural LP relaxation of the MBA problem to obtain the 3/4-approximation. We also give a (3/4-ϵ)-factor algorithm based on the primal-dual schema which runs in Õ(nm) time, for any constant ϵ > 0. [ABSTRACT FROM AUTHOR]

We obtain a 1.5-approximation algorithm for the metric uncapacitated facility location (UFL) problem, which improves on the previously best known 1.52-approximation algorithm by Mahdian, Ye, and Zhang. Note that the approximability lower bound by Guha and Khuller is 1.463 … An algorithm is a (λf ,λc)-approximation algorithm if the solution it produces has total cost at most λf ·F*+λc ·C*, where F* and C* are the facility and the connection cost of an optimal solution. Our new algorithm, which is a modification of the (1 + 2/e)-approximation algorithm of Chudak and Shmoys, is a (1.6774, 1.3738)-approximation algorithm for the UFL problem and is the first one that touches the approximability limit curve (γf ,1+2e-γf) established by Jain, Mahdian, and Saberi. As a consequence, we obtain the first optimal approximation algorithm for instances dominated by connection costs. When combined with a (1.11, 1.7764)-approximation algorithm proposed by Jain et al., and later analyzed by Mahdian et al., we obtain the overall approximation guarantee of 1.5 for the metric UFL problem. We also describe how to use our algorithm to improve the approximation ratio for the 3-level version of UFL. [ABSTRACT FROM AUTHOR]

Let A be a 0/1 matrix of size m × n, and let p be the density of A (i.e., the number of ones divided by m · n). We show that A can be approximated in the cut norm within ϵ · mnp by a sum of cut matrices (of rank 1), where the number of summands is independent of the size m · n of A, provided that A satisfies a certain boundedness condition. This decomposition can be computed in polynomial time. This result extends the work of Frieze and Kannan [Combinatorica, 19 (1999), pp. 175-220] to sparse matrices. As an application, we obtain efficient 1-· approximation algorithms for "bounded" instances of MAX CSP problems. [ABSTRACT FROM AUTHOR]

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

Let ℓ be the number of edges in a longest cycle containing a given vertex v in an undirected graph. We show how to find a cycle through v of length exp(Ω(√log ℓ / log log ℓ )) in polynomial time. This implies the same bound for the longest cycle, longest vw-path, and longest path. The previous best bound for longest path is length Ω(( log ℓ)²/ log log ℓ) due to Björklund and Husfeldt. Our approach, which builds on Björklund and Husfeldt's, uses cycles to enlarge cycles. This self-reducibility allows the approximation method to be iterated. [ABSTRACT FROM AUTHOR]

We give the first algorithmic study of a class of "covering tour" problems related to the geometric traveling salesman problem: Find a polygonal tour for a cutter so that it sweeps out a specified region ("pocket") in order to minimize a cost that depends mainly on the number of turns. These problems arise naturally in manufacturing applications of computational geometry to automatic tool path generation and automatic inspection systems, as well as arc routing ("postman") problems with turn penalties. We prove the NP-completeness of minimum-turn milling and give efficient approximation algorithms for several natural versions of the problem, including a polynomial- time approximation scheme based on a novel adaptation of the m-guillotine method. [ABSTRACT FROM AUTHOR]

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

We consider parallel, identical machine scheduling problems, where the jobs are subject to precedence constraints and release dates, and where the processing times of jobs are governed by independent probability distributions. Our objective is to minimize the expected value of the total weighted completion time. Building upon a linear programming relaxation by Möhring, Schulz, and Uetz [J. ACM, 46 (1999), pp. 924--942] and a delayed list scheduling algorithm by Chekuri et al. [SIAM J. Comput., 31 (2001), pp. 146--166], we derive the first constant-factor approximation algorithms for this model. [ABSTRACT FROM AUTHOR]

We describe logarithmic approximation algorithms for the NP-hard graph optimization problems of minimum linear arrangement, minimum containing interval graph, and minimum storage-time product. This improves upon the best previous approximation bounds of Even, Naor, Rao, and Schieber [J. ACM, 47 (2000), pp. 585-616] for these problems by a factor of &Ohm;(log log n). We use the lower bound provided by the volume W of a spreading metric for each of the ordering problems above (as defined by Even et al.) in order to find a solution with cost at most a logarithmic factor times W for these problems. We develop a divide-and-conquer strategy where the cost of a solution to a problem at a recursive level is C plus the cost of a solution to the subproblems at this level, and where the spreading metric volume on the subproblems is less than the original volume by &Ohm;(C/log n), ensuring that the resulting solution has cost O(log n) times the original spreading metric volume. We note that this is an existentially tight bound on the relationship between the spreading metric volume and the true optimal values for these problems. For planar graphs, we combine a structural theorem of Klein, Plotkin, and Rao [Proceedings of the 25th ACM Symposium on Theory of Computing, 1993, pp. 682-690] with our new recursion technique to show that the spreading metric cost volumes are within an O(log log n) factor of the cost of an optimal solution for the minimum linear arrangement, and the minimum containing interval graph problems. [ABSTRACT FROM AUTHOR]

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

In the survivable network design problem (SNDP), the goal is to find a minimum-cost spanning subgraph satisfying certain connectivity requirements. We study the vertex-connectivity variant of SNDP in which the input specifies, for each pair of vertices, a required number of vertex- disjoint paths connecting them. We give the first strong lower bound on the approximability of SNDP, showing that the problem admits no efficient 2log 1-&epsiv; n ratio approximation for any fixed &epsiv; > 0, unless N P ⊇ DTIME(npolylog(n)). We show hardness of approximation results for some important special cases of SNDP, and we exhibit the first lower bound on the approximability of the related classical NP-hard problem of augmenting the connectivity of a graph using edges from a given set. [ABSTRACT FROM AUTHOR]

We prove the following upper and lower bounds on the exact size of binary space partition (BSP) trees for a set of n isothetic rectangles in the plane: ˙ An upper bound of 3m - 1 in general, and an upper bound of 2n - 1 if the rectangles tile the underlying space. This improves the upper bounds of 4n in [V. Hai Nguyen and P. Widmayer, Binary Space Partitions for Sets of Hyperrectangles, Lecture Notes in Comput. Sci. 1023, Springer-Verlag, Berlin, 1995; F. d'Amore and P. G. Franciosa, Inform. Process. Lett., 44 (1992), pp. 255-2591. A BSP satisfying the upper bounds can be constructed in O(nlogn) time. ˙ A worst-case lower bound of 2n - o(n) in general, and 3nfrac;2 - o(n) if the rectangles form a tiling. The BSP tree is one of the most popular data structures in computational geometry, and hence even "small" factor improvements of 4&frac;3 or 2 on the previously known upper bounds that we show improve the performances of applications relying on the BSP tree. As an illustration, we present improved approximation algorithms for certain dual rectangle tiling problems using our upper bounds on the size of the BSP trees. [ABSTRACT FROM AUTHOR]