The proceedings contain 65 papers. The topics discussed include: a better approximation algorithm for finding planar subgraphs;improving biconnectivity approximation via local optimization;sequential and parallel subq...
ISBN:
(纸本)0898713668
The proceedings contain 65 papers. The topics discussed include: a better approximation algorithm for finding planar subgraphs;improving biconnectivity approximation via local optimization;sequential and parallel subquadratic work algorithms for constructing approximately optimal binary search trees;time and space efficient method-lookup for object-oriented programs;worst-case efficient priority queues;on-line generalized steiner problem;randomized robot navigation algorithms;and scheduling with conflicts, and applications to traffic signal control.
The proceedings contain 53 papers. The topics discussed include: on the approximation of maximum satisfiability;on likely solutions of a stable matching problem+;self-testing polynomial functions efficiently and over ...
ISBN:
(纸本)089791466X
The proceedings contain 53 papers. The topics discussed include: on the approximation of maximum satisfiability;on likely solutions of a stable matching problem+;self-testing polynomial functions efficiently and over rational domains;deciding finiteness of matrix groups in Las Vegas polynomial time;the probabilistic method;approximating the minimum weight triangulation;relative neighborhood graphs in three dimensions;finding a line transversal of axial objects in three dimensions;applications of parametric searching in geometric optimization;and tail estimates for the space complexity of randomized incremental algorithms.
The Lopsided Lovász Local Lemma (LLLL) is a powerful probabilistic principle which has been used in a variety of combinatorial constructions. While this principle began as a general statement about probability sp...
详细信息
We consider the problem of computing a k-sparse approximation to the discrete Fourier transform of an n-dimensional signal. Our main result is a randomized algorithm that computes such an approximation using o(klogn(l...
详细信息
The relative neighborhood graph (RNG) of a set S of n points in M.d is a graph (S, E), where (p, q) ∈ E if and only if there is no point z G S such that max{d(p, z), d(q, z)} 4/3) edges. We present a randomized algor...
ISBN:
(纸本)089791466X
The relative neighborhood graph (RNG) of a set S of n points in M.d is a graph (S, E), where (p, q) ∈ E if and only if there is no point z G S such that max{d(p, z), d(q, z)} < d(p, q). We show that in ℝ3, RNG(S) has O(n4/3) edges. We present a randomized algorithm that constructs RNG(S) in expected time O(n3/2+∈) assuming that the points of S are in general position. If the points of S are arbitrary, the expected running time is P(n7/4+∈). These algorithms can be made deterministic without affecting their asymptotic running time.
We consider an old optimization technique and apply it to the approximation of collections of discrete items. The technique is local improvement search: attempt to extend a collection by adding some items while removi...
详细信息
ISBN:
(纸本)0898713498
We consider an old optimization technique and apply it to the approximation of collections of discrete items. The technique is local improvement search: attempt to extend a collection by adding some items while removing others. We obtain a (κ + l)/2 performance ratio for κ-DM, /c-Set Packing, and Independent Set in κ +1-claw-free graphs by an NC algorithm or in nearly-linear sequential time. It can be extended to fc/2 + e (when κ ≥ 4), and to (κ + l)/3 + e when maximum degree is bounded. We also obtain improved performance ratios for induced subgraph problems, Independent Set in bounded-degree graphs, Vertex Cover in claw-free graphs, Set Cover, and Graph Coloring under a complementary objective function.
We develop a data structure for answering link distance queries between two arbitrary points in a simple polygon. The data structure requires O(n3) time and space for its construction and answers link distance queries...
详细信息
ISBN:
(纸本)089791466X
We develop a data structure for answering link distance queries between two arbitrary points in a simple polygon. The data structure requires O(n3) time and space for its construction and answers link distance queries in O(log n) time. Our result extends to link distance queries between pairs of segments or polygons. We also propose a simpler data structure for computing a link distance approximately, where the error is bounded by a small additive constant. Finally, we also present a scheme for approximating the link and the shortest path distance simultaneously.
We study the question of closeness testing for two discrete distributions. More precisely, given samples from two distributions p and q over an n-element set, we wish to distinguish whether p = q versus p is at least ...
详细信息
While there has been significant progress on algorithmic aspects of the Lovasz Local Lemma (LLL) in recent years, a noteworthy exception is when the LLL is used in the context of random permutations: The "lopside...
详细信息
暂无评论