Reverse greedy is bad for k-center

D. Ellis Hershkowitz; Gregory Kehne

doi:10.1016/j.ipl.2020.105941

Reverse greedy is bad for k-center

D. Ellis Hershkowitz
, Gregory Kehne

Department of Computer Science & Engineering

Research output: Contribution to journal › Article › peer-review

2 Scopus citations

Abstract

We show the reverse greedy algorithm is between a (2k−2)- and a 2k-approximation for k-center.

Original language	English
Article number	105941
Journal	Information Processing Letters
Volume	158
DOIs	https://doi.org/10.1016/j.ipl.2020.105941
State	Published - Jun 2020

Keywords

Approximation algorithms
Combinatorial optimization
Facility location
Reverse greedy

Access to Document

10.1016/j.ipl.2020.105941

Cite this

@article{acb3044c69274c4ba5db5417714662a3,

title = "Reverse greedy is bad for k-center",

abstract = "We show the reverse greedy algorithm is between a (2k−2)- and a 2k-approximation for k-center.",

keywords = "Approximation algorithms, Combinatorial optimization, Facility location, Reverse greedy",

author = "Hershkowitz, \{D. Ellis\} and Gregory Kehne",

note = "Publisher Copyright: {\textcopyright} 2020 Elsevier B.V.",

year = "2020",

month = jun,

doi = "10.1016/j.ipl.2020.105941",

language = "English",

volume = "158",

journal = "Information Processing Letters",

issn = "0020-0190",

}

TY - JOUR

T1 - Reverse greedy is bad for k-center

AU - Hershkowitz, D. Ellis

AU - Kehne, Gregory

PY - 2020/6

Y1 - 2020/6

N2 - We show the reverse greedy algorithm is between a (2k−2)- and a 2k-approximation for k-center.

AB - We show the reverse greedy algorithm is between a (2k−2)- and a 2k-approximation for k-center.

KW - Approximation algorithms

KW - Combinatorial optimization

KW - Facility location

KW - Reverse greedy

UR - https://www.scopus.com/pages/publications/85081117134

U2 - 10.1016/j.ipl.2020.105941

DO - 10.1016/j.ipl.2020.105941

M3 - Article

AN - SCOPUS:85081117134

SN - 0020-0190

VL - 158

JO - Information Processing Letters

JF - Information Processing Letters

M1 - 105941

ER -

Reverse greedy is bad for k-center

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this