Artykuł w czasopiśmie
Brak miniatury
Licencja
Dostęp zamkniętyA Polynomial-Time Approximation Scheme for Facility Location on Planar Graphs
| cris.lastimport.scopus | 2024-02-12T19:35:54Z |
| dc.abstract.en | We consider the classic Facility Location problem on planar graphs (non-uniform, uncapacitated). Given an edge-weighted planar graph G, a set of clients C ⊆ V(G), a set of facilities F ⊆ V(G), and opening costs open: F → R ≥0 , the goal is to find a subset D of F that minimizes Σ cϵC min fϵD dist(c,f) + Σ fϵD open(f). The Facility Location problem remains one of the most classic and fundamental optimization problem for which it is not known whether it admits a polynomial-time approximation scheme (PTAS) on planar graphs despite significant effort for obtaining one. We solve this open problem by giving an algorithm that for any ε>0, computes a solution of cost at most (1+ε) times the optimum in time n (2 O(ε(-2) log(1/ε)) ) . |
| dc.affiliation | Uniwersytet Warszawski |
| dc.conference.country | Stany Zjednoczone |
| dc.conference.datefinish | 2019-11-12 |
| dc.conference.datestart | 2019-11-09 |
| dc.conference.place | Baltimore, Maryland |
| dc.conference.series | IEEE Symposium on Foundations of Computer Science |
| dc.conference.series | IEEE Symposium on Foundations of Computer Science |
| dc.conference.seriesshortcut | FOCS |
| dc.conference.shortcut | FOCS 2019 |
| dc.conference.weblink | http://focs2019.cs.jhu.edu/ |
| dc.contributor.author | Cohen-Addad, Vincent |
| dc.contributor.author | Pilipczuk, Michał |
| dc.contributor.author | Pilipczuk, Marcin |
| dc.date.accessioned | 2024-01-24T18:05:52Z |
| dc.date.available | 2024-01-24T18:05:52Z |
| dc.date.issued | 2019 |
| dc.description.finance | Nie dotyczy |
| dc.identifier.doi | 10.1109/FOCS.2019.00042 |
| dc.identifier.uri | https://repozytorium.uw.edu.pl//handle/item/101791 |
| dc.identifier.weblink | http://xplorestaging.ieee.org/ielx7/8936052/8948505/08948650.pdf?arnumber=8948650 |
| dc.language | eng |
| dc.pbn.affiliation | computer and information sciences |
| dc.relation.pages | 560-581 |
| dc.rights | ClosedAccess |
| dc.sciencecloud | nosend |
| dc.subject.en | facility location |
| dc.subject.en | polynomial-time approximationscheme |
| dc.subject.en | planar metric |
| dc.title | A Polynomial-Time Approximation Scheme for Facility Location on Planar Graphs |
| dc.type | JournalArticle |
| dspace.entity.type | Publication |