Off-line admission control for advance reservations in star networks
| Autor: | Adamy, U., Erlebach, T., Mitsche, D., Schurr, I., Speckmann, B., Welzl, E., Persiano, G., Solis-Oba, R. |
|---|---|
| Přispěvatelé: | Algorithms, Applied Geometric Algorithms |
| Jazyk: | angličtina |
| Rok vydání: | 2005 |
| Předmět: | |
| Zdroj: | Approximation and Online Algorithms ISBN: 9783540245742 WAOA Scopus-Elsevier Approximation and Online Algorithms (2nd International Workshop, WAOA 2004, Bergen, Norway, September 14-16, 2004, Revised Selected Papers), 211-224 STARTPAGE=211;ENDPAGE=224;TITLE=Approximation and Online Algorithms (2nd International Workshop, WAOA 2004, Bergen, Norway, September 14-16, 2004, Revised Selected Papers) |
| ISSN: | 0302-9743 |
| DOI: | 10.1007/978-3-540-31833-0_18 |
| Popis: | Given a network together with a set of connection requests, call admission control is the problem of deciding which calls to accept and which ones to reject in order to maximize the total profit of the accepted requests. We consider call admission control problems with advance reservations in star networks. For the most general variant we present a constant-factor approximation algorithm resolving an open problem due to Erlebach. Our method is randomized and achieves an approximation ratio of 1/18. It can be generalized to accommodate call alternatives, in which case the approximation ratio is 1/24. We show how our method can be derandomized. In addition we prove that call admission control in star networks is ${\mathcal APX}$-hard even for very restricted variants of the problem. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|