This paper presents the following approximation algorithms for computing a minimum cost sequence of planes to cut a convex polyhedron P of n vertices out of a sphere Q: an O(n log n) time O(log(2) n)-factor approximat...
详细信息
ISBN:
(纸本)9783642212048
This paper presents the following approximation algorithms for computing a minimum cost sequence of planes to cut a convex polyhedron P of n vertices out of a sphere Q: an O(n log n) time O(log(2) n)-factor approximation, an O(n(1.5) log n) time O(log n)-factor approximation, and an O(1)-factor approximation with exponential running time. Our results significantly improve upon the previous O(n(3)) time O(log(2) n)-factor approximation solution.
Let G = G(AUB,A x B), with vertical bar A vertical bar =vertical bar B vertical bar = n, be a weighted bipartite graph, and let d(.,.) be the cost function on the edges. Let w(M) denote the weight of a matching in G, ...
详细信息
ISBN:
(纸本)9781450327107
Let G = G(AUB,A x B), with vertical bar A vertical bar =vertical bar B vertical bar = n, be a weighted bipartite graph, and let d(.,.) be the cost function on the edges. Let w(M) denote the weight of a matching in G, and M* a minimum-cost perfect matching in G. We call a perfect matching M c-approximate, for c >= 1, if w(M) <= c . w(M*). We present three approximation algorithms for computing minimum-cost perfect matchings in G. First, we consider the case when d(.,.) is a metric. For any delta > 0, we present an algorithm that, in O(n(2+delta) log n log(2) (1/delta)) time, computes a O(1/delta(alpha))-approximate matching of G, where alpha = log(3) 2 approximate to 0.631. Next, we assume the existence of a dynamic data structure for answering approximate nearest neighbor (ANN) queries under d(.,.). Given two parameters epsilon, delta is an element of (0, 1), we present an algorithm that, in O(epsilon(-2) n(1+delta)tau (n, epsilon) log(2) (n/epsilon) log(1/delta)) time, computes a O(1/delta(alpha))-approximate matching of G, where alpha = 1 + log(2)(1 + epsilon) and tau (n, epsilon) is the query and update time of an (epsilon/2)-ANN data structure. Finally, we present an algorithm that works even if d(.,.) is not a metric but admits an ANN data structure for d(.,.). In particular, we present an algorithm that computes, in O(epsilon(-1)n(3/2)tau(n, epsilon) log(4) (n/epsilon) E) log Delta) time, a (1 + epsilon)-approximate matching of A and B;here Delta is the ratio of the largest to the smallest-cost edge in G, and tau(n, epsilon) is the query and update time of an (epsilon/c)-ANN data structure for some constant c > 1. We show that our results lead to faster matching algorithms for many geometric settings.
One of the greatest successes of computational complexity theory is the classification of countless fundamental computational problems into polynomial-time and NP-hard ones, two classes that are often referred to as t...
详细信息
ISBN:
(纸本)9781450383813
One of the greatest successes of computational complexity theory is the classification of countless fundamental computational problems into polynomial-time and NP-hard ones, two classes that are often referred to as tractable and intractable, respectively. However, this crude distinction of algorithmic efficiency is clearly insufficient when handling today's large scale of data. We need a finer-grained design and analysis of algorithms that pinpoints the exact exponent of polynomial running time, and a better understanding of when a speed-up is not possible. Based on stronger complexity assumptions than P vs NP, like the Strong Exponential Time Hypothesis, recently conditional lower bounds for a variety of fundamental problems in P have been proposed. Unfortunately, these conditional lower bounds often break down when one may settle for a near-optimal solution. Indeed, approximation algorithms can play a significant role when designing fast algorithms not just for traditional NP Hard problems, but also for polynomial time problems. For some applications arising in machine learning, the time complexity of the underlying algorithms is not sufficient to ensure a fast solution. It is often needed to collect side information about the data to ensure high accuracy. This requires low query complexity. In this presentation, we will cover new facets of fast algorithm design for large scale data analysis that emphasizes on the role of developing approximation algorithms for better polynomial time/query complexity.
The Euler genus of a graph is a fundamental and well-studied parameter in graph theory and topology. Computing it has been shown to be NP-hard by Thomassen [23], [24], and it is known to be fixed-parameter tractable. ...
详细信息
ISBN:
(纸本)9780769551357
The Euler genus of a graph is a fundamental and well-studied parameter in graph theory and topology. Computing it has been shown to be NP-hard by Thomassen [23], [24], and it is known to be fixed-parameter tractable. However, the approximability of the Euler genus is wide open. While the existence of an O(1)-approximation is not ruled out, only an O(root n)-approximation [3] is known even in bounded degree graphs. In this paper we give a polynomial-time algorithm which on input a bounded-degree graph of Euler genus g, computes a drawing into a surface of Euler genus g(O(1)) . log (O(1)) n. Combined with the upper bound from [3], our result also implies a O(n(1/2-alpha))-approximation, for some constant alpha > 0. Using our algorithm for approximating the Euler genus as a subroutine, we obtain, in a unified fashion, algorithms with approximation ratios of the form OPTO(1) . log(O(1)) n for several related problems on bounded degree graphs. These include the problems of orientable genus, crossing number, and planar edge and vertex deletion problems. Our algorithm and proof of correctness for the crossing number problem is simpler compared to the long and difficult proof in the recent breakthrough by Chuzhoy [5], while essentially obtaining a qualitatively similar result. For planar edge and vertex deletion problems our results are the first to obtain a bound of form poly(OPT, log n). We also highlight some further applications of our results in the design of algorithms for graphs with small genus. Many such algorithms require that a drawing of the graph is given as part of the input. Our results imply that in several interesting cases, we can implement such algorithms even when the drawing is unknown.
We consider the Max-Buying Problem with Limited Supply, in which there are n items, with C-i copies of each item i, and m bidders such that every bidder b has valuation v(ib) for item i. The goal is to find a pricing ...
详细信息
ISBN:
(纸本)9783642544231
We consider the Max-Buying Problem with Limited Supply, in which there are n items, with C-i copies of each item i, and m bidders such that every bidder b has valuation v(ib) for item i. The goal is to find a pricing p and an allocation of items to bidders that maximize the profit, where every item is allocated to at most C-i bidders, every bidder receives at most one item and if a bidder b receives item i then p(i) <= vib. Briest and Krysta presented a 2-approximation for this problem and Aggarwal et al. presented a 4-approximation for the Price Ladder variant where the pricing must be non-increasing (that is, p(1) >= p(2) >= ... >= p(n)). We present a randomized e/(e-1)-approximation for the Max-Buying Problem with Limited Supply and, for every epsilon > 0, a (2 + epsilon)-approximation for the Price Ladder variant.
This paper studies the design and analysis of approximation algorithms for aggregating preferences over combinatorial domains, represented using Conditional Preference Networks (CP-nets). Its focus is on aggregating p...
详细信息
ISBN:
(纸本)1577358872
This paper studies the design and analysis of approximation algorithms for aggregating preferences over combinatorial domains, represented using Conditional Preference Networks (CP-nets). Its focus is on aggregating preferences over so-called swaps, for which optimal solutions in general are already known to be of exponential size. We first analyze a trivial 2-approximation algorithm that simply outputs the best of the given input preferences, and establish a structural condition under which the approximation ratio of this algorithm is improved to 4/3. We then propose a polynomial-time approximation algorithm whose outputs are provably no worse than those of the trivial algorithm, but often substantially better. A family of problem instances is presented for which our improved algorithm produces optimal solutions, while, for any e, the trivial algorithm cannot attain a (2- epsilon)-approximation. These results may lead to the first polynomial-time approximation algorithm that solves the CP-net aggregation problem for swaps with an approximation ratio substantially better than 2.
We study three complexity parameters that in some sense measure how chordal-like a graph is. The similarity to chordal graphs is used to construct simple polynomial-time approximation algorithms with constant approxim...
详细信息
ISBN:
(纸本)9783642153686
We study three complexity parameters that in some sense measure how chordal-like a graph is. The similarity to chordal graphs is used to construct simple polynomial-time approximation algorithms with constant approximation ratio for many NP-hard problems, when restricted to graphs for which at least one of the three complexity parameters is bounded by a constant. As applications we present approximation algorithms with constant approximation ratio for maximum weighted independent set;minimum (independent) dominating set, minimum vertex coloring, maximum weighted clique, and minimum clique partition for large classes of intersection graphs.
A tree of rings is a network that is obtained by interconnecting rings in a tree structure such that any two rings share at most one node. A connection request (call) in a tree of rings is given by its two endpoints a...
详细信息
ISBN:
(纸本)3540424962
A tree of rings is a network that is obtained by interconnecting rings in a tree structure such that any two rings share at most one node. A connection request (call) in a tree of rings is given by its two endpoints and, in the case of prespecified paths, a path connecting these two endpoints. We study undirected trees of rings as well as bidirected trees of rings. In both cases, we show that the path packing problem (assigning paths to calls so as to minimize the maximum load) can be solved in polynomial time, that the path coloring problem with prespecified paths can be approximated within a constant factor, and that the maximum (weight) edge-disjoint paths problem is NP-hard and can be approximated within a constant factor (no matter whether the paths are prespecified or can be determined by the algorithm). We also consider fault-tolerance in trees of rings: If a set of calls has been established along edge-disjoint paths and if an arbitrary link fails in every ring of the tree of rings, we show that at least one third of the calls can be recovered if rerouting is allowed. Furthermore, computing the optimal number of calls that can be recovered is shown to be polynomial in undirected trees of rings and NP-hard in bidirected trees of rings.
The GENERALIZED MAXIMUM LINEAR ARRANGEMENT PROBLEM is to compute for a given vector x is an element of IRn and an n x n non-negative symmetric matrix w = (w(i,j)), a permutation pi of {1,...,n} that maximizes Sigma (i...
详细信息
ISBN:
(纸本)3540676902
The GENERALIZED MAXIMUM LINEAR ARRANGEMENT PROBLEM is to compute for a given vector x is an element of IRn and an n x n non-negative symmetric matrix w = (w(i,j)), a permutation pi of {1,...,n} that maximizes Sigma (i,j) w(pii,pij)\x(j) - x(i)\. We present a fast 1/3-approximation algorithm for the problem. We also introduce a a-approximation algorithm for MAX k-CUT WITH GIVEN SIZES. This matches the bound obtained by Ageev and Sviridenko, but without using linear programming.
We study the sample placement and shortest tour problem for robots tasked with mapping environmental phenomena modeled as stationary random fields. The objective is to minimize the resources used (samples or tour leng...
详细信息
ISBN:
(纸本)9798350323658
We study the sample placement and shortest tour problem for robots tasked with mapping environmental phenomena modeled as stationary random fields. The objective is to minimize the resources used (samples or tour length) while guaranteeing estimation accuracy. We give approximation algorithms for both problems in convex environments. These improve previously known results, both in terms of theoretical guarantees and in simulations. In addition, we disprove an existing claim in the literature on a lower bound for a solution to the sample placement problem.
暂无评论