Approximation Algorithms

dc.contributor.authorSchulz, Andreas S.
dc.contributor.authorShmoys, David B.
dc.contributor.authorWilliamson, David P.
dc.date.accessioned2021-12-17T10:07:26Z
dc.date.available2021-12-17T10:07:26Z
dc.date.issued1997
dc.description.abstractIncreasing global competition, rapidly changing markets, and greater consumer awareness have altered the way in which corporations do business. To become more efficient, many industries have sought to model some operational aspects by gigantic optimization problems. It is not atypical to encounter models which capture 106 separate "yes" or "no" decisions to be made. Although one could, in principle, try all 210^6 possible solutions to find the optimal one, such a method would be impractically slow. Unfortunately, for most of these models, no algorithms are known that find optimal solutions with reasonable computation times. Typically, industry must rely on solutions of unguaranteed quality that are constructed in an ad hoc manner. Fortunately, for some of these models there are good approximation algorithms: algorithms that produce solutions quickly that are provably close to optimal. Over the past six years, there have been a sequence of major breakthroughs in our understanding of the design of approximation algorithms and of limits to obtaining such performance guarantees: this area has been one of the most flourishing areas of discrete mathematics and theoretical computer science.en
dc.identifier.issn2197-8085
dc.identifier.urihttps://depositonce.tu-berlin.de/handle/11303/15616
dc.identifier.urihttp://dx.doi.org/10.14279/depositonce-14389
dc.language.isoenen
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subject.ddc510 Mathematiken
dc.subject.otherapproximation algorithmen
dc.subject.otheroptimizationen
dc.subject.otheroptimization problemsen
dc.subject.othermodelsen
dc.titleApproximation Algorithmsen
dc.typeResearch Paperen
dc.type.versionsubmittedVersionen
tub.accessrights.dnbfreeen
tub.affiliationFak. 2 Mathematik und Naturwissenschaften>Inst. Mathematikde
tub.affiliation.facultyFak. 2 Mathematik und Naturwissenschaftende
tub.affiliation.instituteInst. Mathematikde
tub.publisher.universityorinstitutionTechnische Universität Berlinen
tub.series.issuenumber1997, 565en
tub.series.namePreprint-Reihe des Instituts für Mathematik, Technische Universität Berlinen
Files
Original bundle
Now showing 1 - 2 of 2
Loading…
Thumbnail Image
Name:
Report-565-1997.pdf
Size:
112.8 KB
Format:
Adobe Portable Document Format
Description:
Loading…
Thumbnail Image
Name:
Report-565-1997.ps
Size:
179.9 KB
Format:
Postscript Files
Description:
Collections