A new approximation technique for resource‐allocation problems
| Autor: | Barna Saha, Aravind Srinivasan |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Linear bottleneck assignment problem
Mathematical optimization 021103 operations research Applied Mathematics General Mathematics Rounding 0211 other engineering and technologies Approximation algorithm Polytope 0102 computer and information sciences 02 engineering and technology 01 natural sciences Computer Graphics and Computer-Aided Design Randomized algorithm 010201 computation theory & mathematics Software Weapon target assignment problem Generalized assignment problem Discrepancy theory Mathematics |
| Zdroj: | Random Structures & Algorithms. 52:680-715 |
| ISSN: | 1098-2418 1042-9832 |
| Popis: | We develop a rounding method based on random walks in polytopes, which leads to improved approximation algorithms and integrality gaps for several assignment problems that arise in resource allocation and scheduling. In particular, it generalizes the work of Shmoys & Tardos on the generalized assignment problem in two different directions, where the machines have hard capacities, and where some jobs can be dropped. We also outline possible applications and connections of this methodology to discrepancy theory and iterated rounding. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Plný text