Better approximation bounds for the joint replenishment problem
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F14%3A10286462" target="_blank" >RIV/00216208:11320/14:10286462 - isvavai.cz</a>
Výsledek na webu
<a href="http://dx.doi.org/10.1137/1.9781611973402.4" target="_blank" >http://dx.doi.org/10.1137/1.9781611973402.4</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1137/1.9781611973402.4" target="_blank" >10.1137/1.9781611973402.4</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Better approximation bounds for the joint replenishment problem
Popis výsledku v původním jazyce
We provide several new approximation results for the joint replenishment problem. In the offline case, we give an algorithm with ratio $approx 1.791$, breaking the barrier of $1.8$. In the online case, we show a lower bound of $approx 2.754$ on the competitive ratio, improving the previous bound of $2.64$. We also study the online version with deadlines, for which we prove that the optimal competitive ratio is $2$.
Název v anglickém jazyce
Better approximation bounds for the joint replenishment problem
Popis výsledku anglicky
We provide several new approximation results for the joint replenishment problem. In the offline case, we give an algorithm with ratio $approx 1.791$, breaking the barrier of $1.8$. In the online case, we show a lower bound of $approx 2.754$ on the competitive ratio, improving the previous bound of $2.64$. We also study the online version with deadlines, for which we prove that the optimal competitive ratio is $2$.
Klasifikace
Druh
D - Stať ve sborníku
CEP obor
IN - Informatika
OECD FORD obor
—
Návaznosti výsledku
Projekt
<a href="/cs/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Centrum excelence - Institut teoretické informatiky (CE-ITI)</a><br>
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Ostatní
Rok uplatnění
2014
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název statě ve sborníku
Proc. of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
ISBN
978-1-61197-338-9
ISSN
—
e-ISSN
—
Počet stran výsledku
13
Strana od-do
42-54
Název nakladatele
ACM-SIAM
Místo vydání
Philadelphia, PA, USA
Místo konání akce
Portland, Oregon, USA
Datum konání akce
5. 1. 2014
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
—