A primal-dual algorithm for online non-uniform facility location

 
This item is provided by the institution :

Repository :
Digital Library of National Technical University of Athens | Dspace@NTUA
see the original item page
in the repository's web site and access all digital files if the item*
share



Semantic enrichment by EKT
Journal part (EN)
Scientific article (EN)
2007 (EN)
A primal-dual algorithm for online non-uniform facility location (EN)
Fotakis, D (EN)
In the online version of Facility Location, the demand points arrive one at a time and must be irrevocably assigned to an open facility upon arrival. The objective is to minimize the sum of facility and assignment costs. We present a simple deterministic primal-dual algorithm for the general case of non-uniform facility costs. We prove that its competitive ratio is (EN)
journalArticle (EN)
Competitive Ratio (EN)
primal-dual algorithm (EN)
Lower Bound (EN)
Online Algorithm (EN)
Facility Location (EN)
Competitive Analysis (EN)
National Technical University of Athens
Digital Library of National Technical University of Athens | Dspace@NTUA
Κεντρική Βιβλιοθήκη Ε.Μ.Π.
Ιδρυματικό Αποθετήριο
Δημοσιεύσεις μελών Δ.Ε.Π. σε περιοδικά
Journal of Discrete Algorithms (EN)
2007 (EN)
http://hdl.handle.net/123456789/27831
10.1016/j.jda.2006.03.001 (EN)



*Institutions are responsible for keeping their URLs functional (digital file, item page in repository site)