New Approximability Results for the Robust k-Median Problem View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2014

AUTHORS

Sayan Bhattacharya , Parinya Chalermsook , Kurt Mehlhorn , Adrian Neumann

ABSTRACT

We consider a variant of the classical k-median problem, introduced by Anthony et al.[1]. In the Robust k-Median problem, we are given an n-vertex metric space (V,d) and m client sets \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\left\{ S_i \subseteq V \right\}_{i=1}^m$\end{document}. We want to open a set F ⊆ V of k facilities such that the worst case connection cost over all client sets is minimized; that is, minimize \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\max_{i}\sum_{v \in S_i} d(F,v)$\end{document}. Anthony et al. showed an O(logm) approximation algorithm for any metric and APX-hardness even in the case of uniform metric. In this paper, we show that their algorithm is nearly tight by providing Ω(logm/ loglogm) approximation hardness, unless \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}${\sf NP} \subseteq \bigcap_{\delta >0} {\sf DTIME}(2^{n^{\delta}})$\end{document}. This result holds even for uniform and line metrics. To our knowledge, this is one of the rare cases in which a problem on a line metric is hard to approximate to within logarithmic factor. We complement the hardness result by an experimental evaluation of different heuristics that shows that very simple heuristics achieve good approximations for realistic classes of instances. More... »

PAGES

50-61

Book

TITLE

Algorithm Theory – SWAT 2014

ISBN

978-3-319-08403-9
978-3-319-08404-6

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-319-08404-6_5

DOI

http://dx.doi.org/10.1007/978-3-319-08404-6_5

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1017948163


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0102", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Applied Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Max-Planck Institut f\u00fcr Informatik, Germany", 
          "id": "http://www.grid.ac/institutes/grid.419528.3", 
          "name": [
            "Max-Planck Institut f\u00fcr Informatik, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Bhattacharya", 
        "givenName": "Sayan", 
        "id": "sg:person.013635477150.68", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013635477150.68"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Max-Planck Institut f\u00fcr Informatik, Germany", 
          "id": "http://www.grid.ac/institutes/grid.419528.3", 
          "name": [
            "Max-Planck Institut f\u00fcr Informatik, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Chalermsook", 
        "givenName": "Parinya", 
        "id": "sg:person.011252741475.62", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011252741475.62"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Max-Planck Institut f\u00fcr Informatik, Germany", 
          "id": "http://www.grid.ac/institutes/grid.419528.3", 
          "name": [
            "Max-Planck Institut f\u00fcr Informatik, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Mehlhorn", 
        "givenName": "Kurt", 
        "id": "sg:person.011757371347.43", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011757371347.43"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Max-Planck Institut f\u00fcr Informatik, Germany", 
          "id": "http://www.grid.ac/institutes/grid.419528.3", 
          "name": [
            "Max-Planck Institut f\u00fcr Informatik, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Neumann", 
        "givenName": "Adrian", 
        "id": "sg:person.010747716435.82", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010747716435.82"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2014", 
    "datePublishedReg": "2014-01-01", 
    "description": "We consider a variant of the classical k-median problem, introduced by Anthony et al.[1]. In the Robust k-Median problem, we are given an n-vertex metric space (V,d) and m client sets \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$\\left\\{ S_i \\subseteq V \\right\\}_{i=1}^m$\\end{document}. We want to open a set F\u2009\u2286\u2009V of k facilities such that the worst case connection cost over all client sets is minimized; that is, minimize \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$\\max_{i}\\sum_{v \\in S_i} d(F,v)$\\end{document}. Anthony et al. showed an O(logm) approximation algorithm for any metric and APX-hardness even in the case of uniform metric. In this paper, we show that their algorithm is nearly tight by providing \u03a9(logm/ loglogm) approximation hardness, unless \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}${\\sf NP} \\subseteq \\bigcap_{\\delta >0} {\\sf DTIME}(2^{n^{\\delta}})$\\end{document}. This result holds even for uniform and line metrics. To our knowledge, this is one of the rare cases in which a problem on a line metric is hard to approximate to within logarithmic factor. We complement the hardness result by an experimental evaluation of different heuristics that shows that very simple heuristics achieve good approximations for realistic classes of instances.", 
    "editor": [
      {
        "familyName": "Ravi", 
        "givenName": "R.", 
        "type": "Person"
      }, 
      {
        "familyName": "G\u00f8rtz", 
        "givenName": "Inge Li", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-319-08404-6_5", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-319-08403-9", 
        "978-3-319-08404-6"
      ], 
      "name": "Algorithm Theory \u2013 SWAT 2014", 
      "type": "Book"
    }, 
    "keywords": [
      "problem", 
      "space", 
      "facilities", 
      "paper", 
      "knowledge", 
      "instances", 
      "et al", 
      "al", 
      "median problem", 
      "set", 
      "connection cost", 
      "cost", 
      "cases", 
      "metrics", 
      "results", 
      "uniform", 
      "line metric", 
      "factors", 
      "evaluation", 
      "heuristics", 
      "simple heuristics", 
      "class", 
      "variants", 
      "k-median problem", 
      "Anthony et al", 
      "Robust k", 
      "metric spaces", 
      "client sets", 
      "k facilities", 
      "approximation algorithm", 
      "algorithm", 
      "uniform metric", 
      "approximation hardness", 
      "hardness", 
      "NPs", 
      "rare case", 
      "logarithmic factor", 
      "hardness results", 
      "experimental evaluation", 
      "different heuristics", 
      "good approximation", 
      "approximation", 
      "realistic class", 
      "new approximability results", 
      "approximability results"
    ], 
    "name": "New Approximability Results for the Robust k-Median Problem", 
    "pagination": "50-61", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1017948163"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-319-08404-6_5"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-319-08404-6_5", 
      "https://app.dimensions.ai/details/publication/pub.1017948163"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-10-01T07:00", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221001/entities/gbq_results/chapter/chapter_67.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-319-08404-6_5"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-08404-6_5'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-08404-6_5'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-08404-6_5'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-08404-6_5'


 

This table displays all metadata directly associated to this object as RDF triples.

130 TRIPLES      22 PREDICATES      70 URIs      63 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-319-08404-6_5 schema:about anzsrc-for:01
2 anzsrc-for:0102
3 schema:author N6fddeb1e4a9344d891f0092d5dbdac2b
4 schema:datePublished 2014
5 schema:datePublishedReg 2014-01-01
6 schema:description We consider a variant of the classical k-median problem, introduced by Anthony et al.[1]. In the Robust k-Median problem, we are given an n-vertex metric space (V,d) and m client sets \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\left\{ S_i \subseteq V \right\}_{i=1}^m$\end{document}. We want to open a set F ⊆ V of k facilities such that the worst case connection cost over all client sets is minimized; that is, minimize \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\max_{i}\sum_{v \in S_i} d(F,v)$\end{document}. Anthony et al. showed an O(logm) approximation algorithm for any metric and APX-hardness even in the case of uniform metric. In this paper, we show that their algorithm is nearly tight by providing Ω(logm/ loglogm) approximation hardness, unless \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}${\sf NP} \subseteq \bigcap_{\delta >0} {\sf DTIME}(2^{n^{\delta}})$\end{document}. This result holds even for uniform and line metrics. To our knowledge, this is one of the rare cases in which a problem on a line metric is hard to approximate to within logarithmic factor. We complement the hardness result by an experimental evaluation of different heuristics that shows that very simple heuristics achieve good approximations for realistic classes of instances.
7 schema:editor N43f37a4377924564b9424ca0ba0bfa19
8 schema:genre chapter
9 schema:isAccessibleForFree true
10 schema:isPartOf Ne84a2dbf52334b6dbfba7645c382ddec
11 schema:keywords Anthony et al
12 NPs
13 Robust k
14 al
15 algorithm
16 approximability results
17 approximation
18 approximation algorithm
19 approximation hardness
20 cases
21 class
22 client sets
23 connection cost
24 cost
25 different heuristics
26 et al
27 evaluation
28 experimental evaluation
29 facilities
30 factors
31 good approximation
32 hardness
33 hardness results
34 heuristics
35 instances
36 k facilities
37 k-median problem
38 knowledge
39 line metric
40 logarithmic factor
41 median problem
42 metric spaces
43 metrics
44 new approximability results
45 paper
46 problem
47 rare case
48 realistic class
49 results
50 set
51 simple heuristics
52 space
53 uniform
54 uniform metric
55 variants
56 schema:name New Approximability Results for the Robust k-Median Problem
57 schema:pagination 50-61
58 schema:productId Nd00804770f1d4e8295e65331959f00c7
59 Nfc7aa94cf1e4417db67c5d5ee3a84fec
60 schema:publisher N162e2e03c4a64677bf83a52cf3846c07
61 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017948163
62 https://doi.org/10.1007/978-3-319-08404-6_5
63 schema:sdDatePublished 2022-10-01T07:00
64 schema:sdLicense https://scigraph.springernature.com/explorer/license/
65 schema:sdPublisher N8b2f995314cd4548820fb218eb81e921
66 schema:url https://doi.org/10.1007/978-3-319-08404-6_5
67 sgo:license sg:explorer/license/
68 sgo:sdDataset chapters
69 rdf:type schema:Chapter
70 N162e2e03c4a64677bf83a52cf3846c07 schema:name Springer Nature
71 rdf:type schema:Organisation
72 N43f37a4377924564b9424ca0ba0bfa19 rdf:first N921ac8ed11174411916a56649d7f7de0
73 rdf:rest Ncb333c73477043079770726c99504431
74 N5ce314c2ca974ca487822538b41cb462 schema:familyName Gørtz
75 schema:givenName Inge Li
76 rdf:type schema:Person
77 N6fddeb1e4a9344d891f0092d5dbdac2b rdf:first sg:person.013635477150.68
78 rdf:rest N7d3a6b50affe4f188484071eee1b0f01
79 N7d3a6b50affe4f188484071eee1b0f01 rdf:first sg:person.011252741475.62
80 rdf:rest N9e744aa8684a4981957461dc14294258
81 N8b2f995314cd4548820fb218eb81e921 schema:name Springer Nature - SN SciGraph project
82 rdf:type schema:Organization
83 N921ac8ed11174411916a56649d7f7de0 schema:familyName Ravi
84 schema:givenName R.
85 rdf:type schema:Person
86 N9e744aa8684a4981957461dc14294258 rdf:first sg:person.011757371347.43
87 rdf:rest Na8379f75f4c143dfa60d95cc792376d9
88 Na8379f75f4c143dfa60d95cc792376d9 rdf:first sg:person.010747716435.82
89 rdf:rest rdf:nil
90 Ncb333c73477043079770726c99504431 rdf:first N5ce314c2ca974ca487822538b41cb462
91 rdf:rest rdf:nil
92 Nd00804770f1d4e8295e65331959f00c7 schema:name doi
93 schema:value 10.1007/978-3-319-08404-6_5
94 rdf:type schema:PropertyValue
95 Ne84a2dbf52334b6dbfba7645c382ddec schema:isbn 978-3-319-08403-9
96 978-3-319-08404-6
97 schema:name Algorithm Theory – SWAT 2014
98 rdf:type schema:Book
99 Nfc7aa94cf1e4417db67c5d5ee3a84fec schema:name dimensions_id
100 schema:value pub.1017948163
101 rdf:type schema:PropertyValue
102 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
103 schema:name Mathematical Sciences
104 rdf:type schema:DefinedTerm
105 anzsrc-for:0102 schema:inDefinedTermSet anzsrc-for:
106 schema:name Applied Mathematics
107 rdf:type schema:DefinedTerm
108 sg:person.010747716435.82 schema:affiliation grid-institutes:grid.419528.3
109 schema:familyName Neumann
110 schema:givenName Adrian
111 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010747716435.82
112 rdf:type schema:Person
113 sg:person.011252741475.62 schema:affiliation grid-institutes:grid.419528.3
114 schema:familyName Chalermsook
115 schema:givenName Parinya
116 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011252741475.62
117 rdf:type schema:Person
118 sg:person.011757371347.43 schema:affiliation grid-institutes:grid.419528.3
119 schema:familyName Mehlhorn
120 schema:givenName Kurt
121 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011757371347.43
122 rdf:type schema:Person
123 sg:person.013635477150.68 schema:affiliation grid-institutes:grid.419528.3
124 schema:familyName Bhattacharya
125 schema:givenName Sayan
126 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013635477150.68
127 rdf:type schema:Person
128 grid-institutes:grid.419528.3 schema:alternateName Max-Planck Institut für Informatik, Germany
129 schema:name Max-Planck Institut für Informatik, Germany
130 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...