A 3/2-approximation algorithm for some minimum-cost graph problems

Basile Couëtoux; James M. Davis; David P. Williamson

doi:10.1007/s10107-013-0727-z

A 3/2-approximation algorithm for some minimum-cost graph problems

Basile Couëtoux, James M. Davis, David P. Williamson

Industrial and Enterprise Systems Engineering

Research output: Contribution to journal › Article › peer-review

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 (Formula presented.)(Formula presented.), and want to find a forest such that each component has at least (Formula presented.)(Formula presented.)vertices. Goemans and Williamson gave a 2-approximation algorithm for this class of problems. We give an improved 3/2-approximation algorithm.

Original language	English (US)
Pages (from-to)	19-34
Number of pages	16
Journal	Mathematical Programming
Volume	150
Issue number	1
DOIs	https://doi.org/10.1007/s10107-013-0727-z
State	Published - Apr 2015

Keywords

05C85
90C27

ASJC Scopus subject areas

Software
Mathematics(all)

Online availability

10.1007/s10107-013-0727-z

Library availability

Discover UIUC Full Text

Cite this

@article{314735918f0e48a3be1fd2d64c3a7e55,

title = "A 3/2-approximation algorithm for some minimum-cost graph problems",

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 (Formula presented.)(Formula presented.), and want to find a forest such that each component has at least (Formula presented.)(Formula presented.)vertices. Goemans and Williamson gave a 2-approximation algorithm for this class of problems. We give an improved 3/2-approximation algorithm.",

keywords = "05C85, 90C27",

author = "Basile Cou{\"e}toux and Davis, {James M.} and Williamson, {David P.}",

note = "Publisher Copyright: {\textcopyright} 2013, Springer-Verlag Berlin Heidelberg and Mathematical Optimization Society.",

year = "2015",

month = apr,

doi = "10.1007/s10107-013-0727-z",

language = "English (US)",

volume = "150",

pages = "19--34",

journal = "Mathematical Programming",

issn = "0025-5610",

publisher = "Springer",

number = "1",

}

TY - JOUR

T1 - A 3/2-approximation algorithm for some minimum-cost graph problems

AU - Couëtoux, Basile

AU - Davis, James M.

AU - Williamson, David P.

PY - 2015/4

Y1 - 2015/4

N2 - 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 (Formula presented.)(Formula presented.), and want to find a forest such that each component has at least (Formula presented.)(Formula presented.)vertices. Goemans and Williamson gave a 2-approximation algorithm for this class of problems. We give an improved 3/2-approximation algorithm.

AB - 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 (Formula presented.)(Formula presented.), and want to find a forest such that each component has at least (Formula presented.)(Formula presented.)vertices. Goemans and Williamson gave a 2-approximation algorithm for this class of problems. We give an improved 3/2-approximation algorithm.

KW - 05C85

KW - 90C27

UR - http://www.scopus.com/inward/record.url?scp=84925289637&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84925289637&partnerID=8YFLogxK

U2 - 10.1007/s10107-013-0727-z

DO - 10.1007/s10107-013-0727-z

M3 - Article

AN - SCOPUS:84925289637

VL - 150

SP - 19

EP - 34

JO - Mathematical Programming

JF - Mathematical Programming

SN - 0025-5610

IS - 1

ER -

A 3/2-approximation algorithm for some minimum-cost graph problems

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this