Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(8)
Approximate Algorithm
Facility Location Problem
Network Design
Random Sampling
Randomized Algorithm
steiner tree problem
Traveling Salesman Problem
Virtual Private Network
Subscribe
Academic
Publications
Deterministic Sampling Algorithms for Network Design
Deterministic Sampling Algorithms for Network Design,10.1007/s004530099344x,Algorithmica,Anke van Zuylen
Edit
Deterministic Sampling Algorithms for Network Design
(
Citations: 1
)
BibTex

RIS

RefWorks
Download
Anke van Zuylen
For several NPhard
network design
problems, the best known approximation algorithms are remarkably simple randomized algorithms called SampleAugment algorithms in Gupta et al. (J. ACM 54(3):11, 2007). The algorithms draw a random sample from the input, solve a certain subproblem on the random sample, and augment the solution for the subproblem to a solution for the original problem. We give a general framework that allows us to derandomize most SampleAugment algorithms, i.e. to specify a specific sample for which the cost of the solution created by the SampleAugment algorithm is at most a constant factor away from optimal. Our approach allows us to give deterministic versions of the SampleAugment algorithms for the connected
facility location
problem, in which the open facilities need to be connected by either a tree or a tour, the
virtual private network
design problem, 2stage rooted stochastic
Steiner tree problem
with independent decisions, the a priori
traveling salesman problem
and the single sink buyatbulk problem. This partially answers an open question posed in Gupta et al. (J. ACM 54(3):11, 2007).
Journal:
Algorithmica
, vol. 60, no. 1, pp. 110151, 2011
DOI:
10.1007/s004530099344x
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
www.springerlink.com
)
(
www.springerlink.com
)
(
dx.doi.org
)
(
www.informatik.unitrier.de
)
(
www.springerlink.com
)
(
www.springerlink.com
)
More »
References
(35)
Local search heuristic for kmedian and facility location problems
(
Citations: 171
)
Vijay Arya
,
Naveen Garg
,
Rohit Khandekar
,
Adam Meyerson
,
Kamesh Munagala
,
Vinayaka Pandit
Conference:
ACM Symposium on Theory of Computing  STOC
, pp. 2129, 2001
Worstcase analysis of a new heuristic for the traveling salesman problem
(
Citations: 274
)
N. Christofides
Published in 1975.
An improved approximation algorithm for virtual private network design
(
Citations: 18
)
Friedrich Eisenbrand
,
Fabrizio Grandoni
Conference:
ACMSIAM Symposium on Discrete Algorithms  SODA
, pp. 928932, 2005
New Approaches for Virtual Private Network Design
(
Citations: 18
)
Friedrich Eisenbrand
,
Fabrizio Grandoni
,
Gianpaolo Oriolo
,
Martin Skutella
Conference:
International Colloquium on Automata, Languages and Programming  ICALP
, pp. 11511162, 2005
Approximating connected facility location problems via random facility sampling and core detouring
(
Citations: 20
)
Friedrich Eisenbrand
,
Fabrizio Grandoni
,
Thomas Rothvoß
,
Guido Schäfer
Conference:
ACMSIAM Symposium on Discrete Algorithms  SODA
, pp. 11741183, 2008
Sort by:
Citations
(1)
One Tree Suffices: A Simultaneous O(1)Approximation for SingleSink BuyatBulk
(
Citations: 1
)
Ashish Goel
,
Ian Post
Journal:
Computing Research Repository  CORR
, vol. abs/1004.2, pp. 593600, 2010