A decade of combinatorial optimization

K.I. Aardal; S. Hoesel, van; J.K. Lenstra; L. Stougie

A decade of combinatorial optimization

K.I. Aardal, S. Hoesel, van, J.K. Lenstra, L. Stougie

Stochastic Operations Research

Research output: Chapter in Book/Report/Conference proceeding › Chapter › Academic › peer-review

Abstract

This paper offers a brief overview of the developments in combinatorial optimization during the past decade. We discuss improvements in polynomial-time algorithms for problems on graphs and networks, and review the methodological and computational progress in linear and integer optimization. Some of the more prominent software packages in these areas are mentioned. With respect to obtaining approximate solutions to NP-hard problems, we survey recent positive and negative results on polynomialtime approximability and summarize the advances in local search.

Original language	English
Title of host publication	Ten years LNMB
Editors	W.K. Klein Haneveld, O.J. Vrieze, L.C.M. Kallenberg
Place of Publication	Amsterdam
Publisher	Centrum voor Wiskunde en Informatica
Pages	5-14
ISBN (Print)	90-6196-475-X
Publication status	Published - 1997

Publication series

Name	CWI Tract
Volume	122

Cite this

@inbook{87ae3fa9e6a94612a860479d2a740b3f,

title = "A decade of combinatorial optimization",

abstract = "This paper offers a brief overview of the developments in combinatorial optimization during the past decade. We discuss improvements in polynomial-time algorithms for problems on graphs and networks, and review the methodological and computational progress in linear and integer optimization. Some of the more prominent software packages in these areas are mentioned. With respect to obtaining approximate solutions to NP-hard problems, we survey recent positive and negative results on polynomialtime approximability and summarize the advances in local search.",

author = "K.I. Aardal and {Hoesel, van}, S. and J.K. Lenstra and L. Stougie",

year = "1997",

language = "English",

isbn = "90-6196-475-X",

series = "CWI Tract",

publisher = "Centrum voor Wiskunde en Informatica",

pages = "5--14",

editor = "{Klein Haneveld}, W.K. and O.J. Vrieze and L.C.M. Kallenberg",

booktitle = "Ten years LNMB",

}

TY - CHAP

T1 - A decade of combinatorial optimization

AU - Aardal, K.I.

AU - Hoesel, van, S.

AU - Lenstra, J.K.

AU - Stougie, L.

PY - 1997

Y1 - 1997

N2 - This paper offers a brief overview of the developments in combinatorial optimization during the past decade. We discuss improvements in polynomial-time algorithms for problems on graphs and networks, and review the methodological and computational progress in linear and integer optimization. Some of the more prominent software packages in these areas are mentioned. With respect to obtaining approximate solutions to NP-hard problems, we survey recent positive and negative results on polynomialtime approximability and summarize the advances in local search.

AB - This paper offers a brief overview of the developments in combinatorial optimization during the past decade. We discuss improvements in polynomial-time algorithms for problems on graphs and networks, and review the methodological and computational progress in linear and integer optimization. Some of the more prominent software packages in these areas are mentioned. With respect to obtaining approximate solutions to NP-hard problems, we survey recent positive and negative results on polynomialtime approximability and summarize the advances in local search.

M3 - Chapter

SN - 90-6196-475-X

T3 - CWI Tract

SP - 5

EP - 14

BT - Ten years LNMB

A2 - Klein Haneveld, W.K.

A2 - Vrieze, O.J.

A2 - Kallenberg, L.C.M.

PB - Centrum voor Wiskunde en Informatica

CY - Amsterdam

ER -

A decade of combinatorial optimization

Abstract

Publication series

Fingerprint

Cite this