Anzeige
Erschienen in:
2002 | OriginalPaper | Buchkapitel
Improved Approximation Algorithms for Resource Allocation
verfasst von : Gruia Calinescu, Amit Chakrabarti, Howard Karloff, Yuval Rabani
Erschienen in: Integer Programming and Combinatorial Optimization
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We study the problem of finding a most profitable subset of n given tasks, each with a given start and finish time as well as profit and resource requirement, that at no time exceeds the quantity B of available resource. We show that this NP-hard Resource Allocation problem can be (1/2 - ε)-approximated in polynomial time, which improves upon earlier approximation results for this problem, the best previously published result being a 1/4-approximation. We also give a simpler and faster 1/3-approximation algorithm.