ZIB

1

Electronic Resource

Approximation Algorithms for Certain Network Improvement Problems (1998)

Krumke, Sven O. ; Marathe, Madhav V. ; Noltemeier, Hartmut ; [et al.]

Springer

Journal of combinatorial optimization 2 (1998), S. 257-288

add to mindlist on the mindlist

Details

ISSN: 1573-2886

Keywords: Complexity ; NP-hardness ; Approximation Algorithms

Source: Springer Online Journal Archives 1860-2000

Topics: Mathematics

Notes: Abstract We study budget constrained network upgrading problems. Such problems aim at finding optimal strategies for improving a network under some cost measure subject to certain budget constraints. Given an edge weighted graph G = (V, E), in the edge based upgrading model, it is assumed that each edge e of the given network also has an associated function ce (t) that specifies the cost of upgrading the edge by an amount t. A reduction strategy specifies for each edge e the amount by which the length ℓ(e) is to be reduced. In the node based upgrading model, a node v can be upgraded at an expense of c(v). Such an upgrade reduces the delay of each edge incident on v. For a given budget B, the goal is to find an improvement strategy such that the total cost of reduction is at most the given budget B and the cost of a subgraph (e.g. minimum spanning tree) under the modified edge lengths is the best over all possible strategies which obey the budget constraint. After providing a brief overview of the models and definitions of the various problems considered, we present several new results on the complexity and approximability of network improvement problems.

Type of Medium: Electronic Resource

URL: http://dx.doi.org/10.1023/A:1009798010579

Permalink

Library	Location	Call Number	Volume/Issue/Year	Availability

Others were also interested in ...

Paper (German National Licenses)

Fulltext

2

Book

Online optimization : competitive analysis and beyond; 02-25 (2002)

Krumke, Sven O.

Berlin :Konrad-Zuse-Zentrum,

add to mindlist on the mindlist

Details

Title: Online optimization : competitive analysis and beyond; 02-25

Author: Krumke, Sven O.

Publisher: Berlin :Konrad-Zuse-Zentrum,

Year of publication: 2002

Pages: 176 S.

Series Statement: ZIB-Report 02-25

Type of Medium: Book

Permalink

Library	Location	Call Number	Volume/Issue/Year	Availability

Others were also interested in ...

ZIB Catalog

Zuse Institute Berlin

3

Book

Online optimization of large scale systems (2001)

Grötschel, Martin [[Hrsg.]] ; Krumke, Sven O. [[Hrsg.]] ; Rambau, Jörg [[Hrsg.]]

Berlin u.a. :Springer,

add to mindlist on the mindlist

Details

Title: Online optimization of large scale systems

Contributer: Grötschel, Martin , Krumke, Sven O. , Rambau, Jörg

Publisher: Berlin u.a. :Springer,

Year of publication: 2001

Pages: 801 S.

Type of Medium: Book

Permalink

Library	Location	Call Number	Volume/Issue/Year	Availability

Others were also interested in ...

ZIB Catalog

Zuse Institute Berlin

4

Book

Simulation Studies for the Online-Dial-a-Ride Problem /; Preprint SC 99-09 (1999)

Grötschel, Martin ; Hauptmeier, Dietrich ; Krumke, Sven O. ; [et al.]

Berlin :Konrad-Zuse-Zentrum für Informationstechnik,

add to mindlist on the mindlist

Details

Title: Simulation Studies for the Online-Dial-a-Ride Problem /; Preprint SC 99-09

Author: Grötschel, Martin

Contributer: Hauptmeier, Dietrich , Krumke, Sven O. , Rambau, Jörg

Publisher: Berlin :Konrad-Zuse-Zentrum für Informationstechnik,

Year of publication: 1999

Pages: 12 S.

Series Statement: Preprint / Konrad-Zuse-Zentrum für Informationstechnik Berlin Preprint SC 99-09

ISSN: 0933-7911

Type of Medium: Book

Language: English

URL: http://opus.kobv.de/zib/volltexte/1999/398/

Permalink

Library	Location	Call Number	Volume/Issue/Year	Availability

Others were also interested in ...

ZIB Catalog

Zuse Institute Berlin

5

Book

Combinatorial Online Optimization /; Preprint SC 98-24 (1998)

Ascheuer, Norbert ; Grötschel, Martin ; Krumke, Sven O. ; [et al.]

Berlin :Konrad-Zuse-Zentrum für Informationstechnik,

add to mindlist on the mindlist

Details

Title: Combinatorial Online Optimization /; Preprint SC 98-24

Author: Ascheuer, Norbert

Contributer: Grötschel, Martin , Krumke, Sven O. , Rambau, Jörg

Publisher: Berlin :Konrad-Zuse-Zentrum für Informationstechnik,

Year of publication: 1998

Pages: 24 S.

Series Statement: Preprint / Konrad-Zuse-Zentrum für Informationstechnik Berlin Preprint SC 98-24

ISSN: 0933-7911

Type of Medium: Book

Language: English

URL: http://opus.kobv.de/zib/volltexte/1998/368/

Permalink

Library	Location	Call Number	Volume/Issue/Year	Availability

Others were also interested in ...

ZIB Catalog

Zuse Institute Berlin

6

Book

¬The¬ Online Transportation Problem: Competitive Scheduling of Elevators /; Preprint SC 98-34 (1998)

Ascheuer, Norbert ; Krumke, Sven O. ; Rambau, Jörg

Berlin :Konrad-Zuse-Zentrum für Informationstechnik,

add to mindlist on the mindlist

Details

Title: ¬The¬ Online Transportation Problem: Competitive Scheduling of Elevators /; Preprint SC 98-34

Author: Ascheuer, Norbert

Contributer: Krumke, Sven O. , Rambau, Jörg

Publisher: Berlin :Konrad-Zuse-Zentrum für Informationstechnik,

Year of publication: 1998

Pages: 16 S.

Series Statement: Preprint / Konrad-Zuse-Zentrum für Informationstechnik Berlin Preprint SC 98-34

ISSN: 0933-7911

Type of Medium: Book

Language: English

URL: http://opus.kobv.de/zib/volltexte/1998/378/

Permalink

Library	Location	Call Number	Volume/Issue/Year	Availability

Others were also interested in ...

ZIB Catalog

Zuse Institute Berlin

7

Book

Euler is Standing in Line /; Preprint SC 99-06 (1999)

Hauptmeier, Dietrich ; Krumke, Sven O. ; Rambau, Jörg ; [et al.]

Berlin :Konrad-Zuse-Zentrum für Informationstechnik,

add to mindlist on the mindlist

Details

Title: Euler is Standing in Line /; Preprint SC 99-06

Author: Hauptmeier, Dietrich

Contributer: Krumke, Sven O. , Rambau, Jörg , Wirth., Hans-Christoph

Publisher: Berlin :Konrad-Zuse-Zentrum für Informationstechnik,

Year of publication: 1999

Pages: 24 S.

Series Statement: Preprint / Konrad-Zuse-Zentrum für Informationstechnik Berlin Preprint SC 99-06

ISSN: 0933-7911

Type of Medium: Book

Language: English

URL: http://opus.kobv.de/zib/volltexte/1999/395/

Permalink

Library	Location	Call Number	Volume/Issue/Year	Availability

Others were also interested in ...

ZIB Catalog

Zuse Institute Berlin

8

Book

¬The¬ Online Dial-a-Ride Problem under Reasonable Load /; Preprint SC 99-08 (1999)

Hauptmeier, Dietrich ; Krumke, Sven O. ; Rambau, Jörg

Berlin :Konrad-Zuse-Zentrum für Informationstechnik,

add to mindlist on the mindlist

Details

Title: ¬The¬ Online Dial-a-Ride Problem under Reasonable Load /; Preprint SC 99-08

Author: Hauptmeier, Dietrich

Contributer: Krumke, Sven O. , Rambau, Jörg

Publisher: Berlin :Konrad-Zuse-Zentrum für Informationstechnik,

Year of publication: 1999

Pages: 12 S.

Series Statement: Preprint / Konrad-Zuse-Zentrum für Informationstechnik Berlin Preprint SC 99-08

ISSN: 0933-7911

Type of Medium: Book

Language: English

URL: http://opus.kobv.de/zib/volltexte/1999/397/

Permalink

Library	Location	Call Number	Volume/Issue/Year	Availability

Others were also interested in ...

ZIB Catalog

Zuse Institute Berlin

9

Book

Budgeted Maximal Graph Coverage /; ZIB-Report 02-24 (2002)

Krumke, Sven O. ; Marathe, Madhav V. ; Poensgen, Diana ; [et al.]

Berlin :Konrad-Zuse-Zentrum für Informationstechnik,

add to mindlist on the mindlist

Details

Title: Budgeted Maximal Graph Coverage /; ZIB-Report 02-24

Author: Krumke, Sven O.

Contributer: Marathe, Madhav V. , Poensgen, Diana , Ravi, Sekharipuram S. , Wirth, Hans-Christoph

Publisher: Berlin :Konrad-Zuse-Zentrum für Informationstechnik,

Year of publication: 2002

Series Statement: ZIB-Report ZIB-Report 02-24

ISSN: 1438-0064

Type of Medium: Book

Language: English

URL: http://opus.kobv.de/zib/volltexte/2002/692/

Permalink

Library	Location	Call Number	Volume/Issue/Year	Availability

Others were also interested in ...

ZIB Catalog

Zuse Institute Berlin

10

Book

Online Optimization: Competitive Analysis and Beyond /; ZIB-Report 02-25 (2002)

Krumke, Sven O.

Berlin :Konrad-Zuse-Zentrum für Informationstechnik,

add to mindlist on the mindlist

Details

Title: Online Optimization: Competitive Analysis and Beyond /; ZIB-Report 02-25

Author: Krumke, Sven O.

Publisher: Berlin :Konrad-Zuse-Zentrum für Informationstechnik,

Year of publication: 2002

Series Statement: ZIB-Report ZIB-Report 02-25

ISSN: 1438-0064

Type of Medium: Book

Language: English

URL: http://opus.kobv.de/zib/volltexte/2002/693/

Permalink

Library	Location	Call Number	Volume/Issue/Year	Availability

Others were also interested in ...

ZIB Catalog

Zuse Institute Berlin