Improved Approximation Guarantees for Lower-Bounded Facility Location
| Autor: | Sara Ahmadian, Chaitanya Swamy |
|---|---|
| Rok vydání: | 2013 |
| Předmět: |
Mathematical optimization
Current (mathematics) Demand point Generalization 0102 computer and information sciences 02 engineering and technology 01 natural sciences Facility location problem Open facility 010201 computation theory & mathematics Bounded function 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Mathematics |
| Zdroj: | Approximation and Online Algorithms ISBN: 9783642380150 WAOA |
| Popis: | We consider the lower-bounded facility location (LBFL) problem, which is a generalization of uncapacitated facility location (UFL), where each open facility is required to serve a certain minimum amount of demand. The current best approximation ratio for LBFL is 448 [17]. We substantially advance the state-of-the-art for LBFL by improving its approximation ratio from 448 [17] to 82.6. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|