Network design and improvement

Authors
Noltemeier, H Wirth, HC Krumke, SO
Citation
H. Noltemeier et al., Network design and improvement, ACM C SURV, 31, 1999, pp. 1-5
Citations number
23
Categorie Soggetti
Computer Science & Engineering
Journal title
ACM COMPUTING SURVEYS
ISSN journal
03600300 → ACNP
Volume
31
Year of publication
1999
Supplement
3
Pages
1 - 5
Database
ISI
SICI code
0360-0300(199909)31:<1:NDAI>2.0.ZU;2-U
Abstract
Inspired by the fact that many combinatorial optimization problems arising in practice are NP-hard, the design of efficient approximation algorithms h as been a major research topic for the last years. Since we can not expect to solve any NP-hard problem in polynomial time, it is meaningful to compro mise optimality of a solution and settle for a "sufficiently good" solution that can be computed efficiently in polynomial time.