Abstract
We study simple greedy approximation algorithms for general class of integer packing problems. We provide a novel analysis based on the duality theory of linear programming. This enables to significantly improve on the approximation ratios of these greedy methods, and gives a unified analysis of greedy for many packing problems. We show matching lower bounds on the ratios of such greedy methods. Applications to some specific problems, including mechanism design for combinatorial auctions, are also shown.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 615-627 |
| Number of pages | 13 |
| Journal | Lecture Notes in Computer Science |
| Volume | 3618 |
| DOIs | |
| State | Published - 2005 |
| Externally published | Yes |
| Event | 30th International Symposium on Mathematical Foundations of Computer Science 2005, MFCS 2005 - Gdansk, Poland Duration: Aug 29 2005 → Sep 2 2005 |
ASJC Scopus subject areas
- Theoretical Computer Science
- General Computer Science