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

 
δείτε την πρωτότυπη σελίδα τεκμηρίου
στον ιστότοπο του αποθετηρίου του φορέα για περισσότερες πληροφορίες και για να δείτε όλα τα ψηφιακά αρχεία του τεκμηρίου*
κοινοποιήστε το τεκμήριο



A primal-dual algorithm for online non-uniform facility location (EN)

Fotakis, D (EN)

N/A (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

Competitive Ratio (EN)
primal-dual algorithm (EN)
Lower Bound (EN)
Online Algorithm (EN)
Facility Location (EN)
Competitive Analysis (EN)

Εθνικό Μετσόβιο Πολυτεχνείο (EL)
National Technical University of Athens (EN)

Journal of Discrete Algorithms (EN)

2007


N/A (EN)



*Η εύρυθμη και αδιάλειπτη λειτουργία των διαδικτυακών διευθύνσεων των συλλογών (ψηφιακό αρχείο, καρτέλα τεκμηρίου στο αποθετήριο) είναι αποκλειστική ευθύνη των αντίστοιχων Φορέων περιεχομένου.