Approximating minimum-cost connectivity problems

Guy Kortsarz; Zeev Nutov

doi:10.1201/9781420010749

Approximating minimum-cost connectivity problems

Guy Kortsarz, Zeev Nutov

Rutgers Camden, Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Chapter

81 Scopus citations

Abstract

We survey approximation algorithms and hardness results for versions of the Generalized Steiner Network (GSN) probleminwhichwe seek tofind a low-cost subgraph (where the cost of a subgraph is the sum of the costs of its edges) that satisfies prescribed connectivity requirements. These problems include the following well-known problems: min-cost k-flow, min-cost spanning tree, traveling salesman, directed/undirected Steiner tree, Steiner forest, k-edge/node-connected spanning subgraph, and others.

Original language	English (US)
Title of host publication	Handbook of Approximation Algorithms and Metaheuristics
Publisher	CRC Press
Pages	58-1-58-22
ISBN (Electronic)	9781420010749
ISBN (Print)	1584885505, 9781584885504
DOIs	https://doi.org/10.1201/9781420010749
State	Published - Jan 1 2007

All Science Journal Classification (ASJC) codes

Computer Science(all)

Access to Document

10.1201/9781420010749

Cite this

@inbook{bee7f68854ca4b0390fd4ab60a255b86,

title = "Approximating minimum-cost connectivity problems",

abstract = "We survey approximation algorithms and hardness results for versions of the Generalized Steiner Network (GSN) probleminwhichwe seek tofind a low-cost subgraph (where the cost of a subgraph is the sum of the costs of its edges) that satisfies prescribed connectivity requirements. These problems include the following well-known problems: min-cost k-flow, min-cost spanning tree, traveling salesman, directed/undirected Steiner tree, Steiner forest, k-edge/node-connected spanning subgraph, and others.",

author = "Guy Kortsarz and Zeev Nutov",

note = "Publisher Copyright: {\textcopyright} 2007 by Taylor & Francis Group, LLC.",

year = "2007",

month = jan,

day = "1",

doi = "10.1201/9781420010749",

language = "English (US)",

isbn = "1584885505",

pages = "58--1--58--22",

booktitle = "Handbook of Approximation Algorithms and Metaheuristics",

publisher = "CRC Press",

}

TY - CHAP

T1 - Approximating minimum-cost connectivity problems

AU - Kortsarz, Guy

AU - Nutov, Zeev

PY - 2007/1/1

Y1 - 2007/1/1

N2 - We survey approximation algorithms and hardness results for versions of the Generalized Steiner Network (GSN) probleminwhichwe seek tofind a low-cost subgraph (where the cost of a subgraph is the sum of the costs of its edges) that satisfies prescribed connectivity requirements. These problems include the following well-known problems: min-cost k-flow, min-cost spanning tree, traveling salesman, directed/undirected Steiner tree, Steiner forest, k-edge/node-connected spanning subgraph, and others.

AB - We survey approximation algorithms and hardness results for versions of the Generalized Steiner Network (GSN) probleminwhichwe seek tofind a low-cost subgraph (where the cost of a subgraph is the sum of the costs of its edges) that satisfies prescribed connectivity requirements. These problems include the following well-known problems: min-cost k-flow, min-cost spanning tree, traveling salesman, directed/undirected Steiner tree, Steiner forest, k-edge/node-connected spanning subgraph, and others.

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

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

U2 - 10.1201/9781420010749

DO - 10.1201/9781420010749

M3 - Chapter

AN - SCOPUS:48549091072

SN - 1584885505

SN - 9781584885504

SP - 58-1-58-22

BT - Handbook of Approximation Algorithms and Metaheuristics

PB - CRC Press

ER -

Approximating minimum-cost connectivity problems

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this