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)


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)


N/A (EN)

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