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-12-01T06:46", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221201/entities/gbq_results/chapter/chapter_108.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 N439354cb540d4de589e643366df4c7b8
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 Nb6934402f33243298ff62d6197d76dd0
8 schema:genre chapter
9 schema:isAccessibleForFree true
10 schema:isPartOf N2faa1d8cb5264dd1ae573a07fb449b1d
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 N0efaadaef747407ea2863ade2485557b
59 Nf80fd9721bd14ffebcad9cf33ac28bc0
60 schema:publisher N6e8bc497799b4f1e80590b1a6cd9b575
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-12-01T06:46
64 schema:sdLicense https://scigraph.springernature.com/explorer/license/
65 schema:sdPublisher Nd583eca5159e45d89dea457b5a0f3a3e
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 N0efaadaef747407ea2863ade2485557b schema:name doi
71 schema:value 10.1007/978-3-319-08404-6_5
72 rdf:type schema:PropertyValue
73 N2faa1d8cb5264dd1ae573a07fb449b1d schema:isbn 978-3-319-08403-9
74 978-3-319-08404-6
75 schema:name Algorithm Theory – SWAT 2014
76 rdf:type schema:Book
77 N439354cb540d4de589e643366df4c7b8 rdf:first sg:person.013635477150.68
78 rdf:rest N8811e3f12c23440faa9f32eecfcafaa8
79 N6e8bc497799b4f1e80590b1a6cd9b575 schema:name Springer Nature
80 rdf:type schema:Organisation
81 N712f6f46176b49cbb177a8390fd1ede4 schema:familyName Gørtz
82 schema:givenName Inge Li
83 rdf:type schema:Person
84 N72233d120b1645e992391d2911c8256a rdf:first sg:person.010747716435.82
85 rdf:rest rdf:nil
86 N769f684cf07b4c2e87cb70a591c64021 rdf:first N712f6f46176b49cbb177a8390fd1ede4
87 rdf:rest rdf:nil
88 N8811e3f12c23440faa9f32eecfcafaa8 rdf:first sg:person.011252741475.62
89 rdf:rest Nd8846914a82b4dc9862fd438b123e3f4
90 Nb6934402f33243298ff62d6197d76dd0 rdf:first Ne7986229806a45a38b71a7a447bd8b9b
91 rdf:rest N769f684cf07b4c2e87cb70a591c64021
92 Nd583eca5159e45d89dea457b5a0f3a3e schema:name Springer Nature - SN SciGraph project
93 rdf:type schema:Organization
94 Nd8846914a82b4dc9862fd438b123e3f4 rdf:first sg:person.011757371347.43
95 rdf:rest N72233d120b1645e992391d2911c8256a
96 Ne7986229806a45a38b71a7a447bd8b9b schema:familyName Ravi
97 schema:givenName R.
98 rdf:type schema:Person
99 Nf80fd9721bd14ffebcad9cf33ac28bc0 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)


...