Name
Abstract | ||
|---|---|---|
We consider a class of graph problems introduced in a paper of Goemans and Williamson that involve finding forests of minimum edge cost. This class includes a number of location/routing problems; it also includes a problem in which we are given as input a parameter $$k$$ k , and want to find a forest such that each component has at least $$k$$ k vertices. Goemans and Williamson gave a 2-approximation algorithm for this class of problems. We give an improved 3/2-approximation algorithm. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1007/s10107-013-0727-z | Mathematical Programming: Series A and B |
Keywords | Field | DocType |
90C27, 05C85 | Discrete mathematics,Approximation algorithm,Graph,Mathematical optimization,Combinatorics,Vertex (geometry),Mathematics | Journal |
Volume | Issue | ISSN |
150 | 1 | 1436-4646 |
Citations | PageRank | References |
0 | 0.34 | 9 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Basile Couëtoux | 1 | 0 | 0.34 |
| James M. Davis | 2 | 36 | 4.27 |
| David P. Williamson | 3 | 3564 | 413.34 |