Robert Carr
- 1.R. Cart and S. Vempala. Towards a 4/3 approximation for the asymmetric traveling salesman problem. In SODA Conference Proceedings, 2000. Google Scholar
Digital Library
- 2.J. Cheriyan, A. Sebo, and Z.Szigeti. Improving on the 1.5-approximation of a smallest 2-edge connected spanning subgraph, in IPCO Conference Proceedings, 1998.Google Scholar
- 3.T. Hagerup and C. Rub. A guided tour of chernoff bounds. Information Processing Letters, 33(6):305-308, 1990. Google ScholarDigital Library
- 4.P. Raghavan and C. Thompson. Randomized rounding: a technique for provably good algorithms and algorithmic proofs. Combinatorica, 7(4):365-374, 1987. Google ScholarDigital Library
- 5.P. Raghavan and C. Thompson. Multiterminal global routing: a deterministic approximation scheme. Algorithrnica, 6:73-82, 1991.Google ScholarDigital Library
- 6.S. Vempala and B. Voecking. Approximating multicast congestion. In ISAAC Proceedings, 1999.Google ScholarCross Ref
Index Terms
- Randomized metarounding (extended abstract)
Recommendations
Near-optimal distortion bounds for embedding doubling spaces into L1
STOC '11: Proceedings of the forty-third annual ACM symposium on Theory of computingWe exhibit an infinite doubling metric space (X,d) such that for any non-expansive f : X -> L1, there exists a pair x,y ∈ X with d(x,y) arbitrarily large, and such that |f(x)-f(y)\|1/d(x,y) ≲ √log log d(x,y)}/(log d(x,y)).
As a consequence, we show that ...
An optimal randomized logarithmic time connectivity algorithm for the EREW PRAM (extended abstract)
SPAA '94: Proceedings of the sixth annual ACM symposium on Parallel algorithms and architecturesImproving a long chain of works we obtain a randomized EREW PRAM algorithm for finding the connected components of a graph G=(V,E) with n vertices and m edges in O(log n) time using an optimal number of O((m+n)/log n) processors. The result returned by ...
Randomized metarounding
Probabilistic methods in combinatorial optimizationLet P be a linear relaxation of an integer polytope Z such that the integrality gap of P with respect to Z is at most r, as verified by a polytime heuristic A, which on any positive cost function c returns an integer solution (an extreme point of Z) ...
Comments