The ordered k-median problem: surrogate models and approximation algorithms View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2018-03-16

AUTHORS

Ali Aouad, Danny Segev

ABSTRACT

In the last two decades, a steady stream of research has been devoted to studying various computational aspects of the ordered k-median problem, which subsumes traditional facility location problems (such as median, center, p-centrum, etc.) through a unified modeling approach. Given a finite metric space, the objective is to locate k facilities in order to minimize the ordered median cost function. In its general form, this function penalizes the coverage distance of each vertex by a multiplicative weight, depending on its ranking (or percentile) in the ordered list of all coverage distances. While antecedent literature has focused on mathematical properties of ordered median functions, integer programming methods, various heuristics, and special cases, this problem was not studied thus far through the lens of approximation algorithms. In particular, even on simple network topologies, such as trees or line graphs, obtaining non-trivial approximation guarantees is an open question. The main contribution of this paper is to devise the first provably-good approximation algorithms for the ordered k-median problem. We develop a novel approach that relies primarily on a surrogate model, where the ordered median function is replaced by a simplified ranking-invariant functional form, via efficient enumeration. Surprisingly, while this surrogate model is Ω(nΩ(1))-hard to approximate on general metrics, we obtain an O(logn)-approximation for our original problem by employing local search methods on a smooth variant of the surrogate function. In addition, an improved guarantee of 2+ϵ is obtained on tree metrics by optimally solving the surrogate model through dynamic programming. Finally, we show that the latter optimality gap is tight up to an O(ϵ) term. More... »

PAGES

1-29

References to SciGraph publications

  • 2005-06. Thep-facility ordered median problem on networks in TOP
  • 2005-04. Heuristic Procedures for Solving the Discrete Ordered Median Problem in ANNALS OF OPERATIONS RESEARCH
  • 2001. Discrete Ordered Weber Problems in OPERATIONS RESEARCH PROCEEDINGS 2000
  • 2015. Location Science in NONE
  • 2010-09. Maximum gradient embeddings and monotone clustering in COMBINATORICA
  • 2017-10. Revisiting k-sum optimization in MATHEMATICAL PROGRAMMING
  • 2009-10. Constructing a DC decomposition for ordered median problems in JOURNAL OF GLOBAL OPTIMIZATION
  • 2003-09. Robust discrete optimization and network flows in MATHEMATICAL PROGRAMMING
  • 2005-03. Locating tree-shaped facilities using the ordered median objective in MATHEMATICAL PROGRAMMING
  • 2012-02. An inverse approach to convex ordered median problems in trees in JOURNAL OF COMBINATORIAL OPTIMIZATION
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s10107-018-1259-3

    DOI

    http://dx.doi.org/10.1007/s10107-018-1259-3

    DIMENSIONS

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


    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/0102", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Applied Mathematics", 
            "type": "DefinedTerm"
          }, 
          {
            "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"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "London Business School", 
              "id": "https://www.grid.ac/institutes/grid.14868.33", 
              "name": [
                "London Business School, NW1 4SA, London, UK"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Aouad", 
            "givenName": "Ali", 
            "id": "sg:person.010255531614.72", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010255531614.72"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Haifa", 
              "id": "https://www.grid.ac/institutes/grid.18098.38", 
              "name": [
                "Department of Statistics, University of Haifa, 31905, Haifa, Israel"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Segev", 
            "givenName": "Danny", 
            "id": "sg:person.016117407141.65", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016117407141.65"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1145/509907.510012", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1001857295"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02578990", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1004867366", 
              "https://doi.org/10.1007/bf02578990"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02578990", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1004867366", 
              "https://doi.org/10.1007/bf02578990"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/301250.301257", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006383282"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-319-13111-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006415661", 
              "https://doi.org/10.1007/978-3-319-13111-5"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-319-13111-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006415661", 
              "https://doi.org/10.1007/978-3-319-13111-5"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1002/(sici)1097-0037(199912)34:4<283::aid-net8>3.0.co;2-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006604005"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-56656-1_12", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006992019", 
              "https://doi.org/10.1007/978-3-642-56656-1_12"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-56656-1_12", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006992019", 
              "https://doi.org/10.1007/978-3-642-56656-1_12"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.ejor.2008.02.033", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1009793253"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.ejor.2006.09.069", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010447297"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.ejor.2016.10.016", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010660638"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.cor.2008.08.019", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1012000925"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.cor.2005.03.025", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1018119569"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1006/jagm.2000.1100", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019452982"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1002/(sici)1097-0037(199812)32:4<255::aid-net2>3.0.co;2-o", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1020119512"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00493-010-2302-z", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1021005060", 
              "https://doi.org/10.1007/s00493-010-2302-z"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.ejor.2013.09.029", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1023113952"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10878-010-9353-3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1024266334", 
              "https://doi.org/10.1007/s10878-010-9353-3"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0166-218x(00)00253-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1026610330"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1177/0160017612450710", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1026839070"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1177/0160017612450710", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1026839070"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10898-008-9326-6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1027809022", 
              "https://doi.org/10.1007/s10898-008-9326-6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/375827.375845", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028995883"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0020-0190(92)90208-d", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1029425565"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10107-016-1096-1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032110827", 
              "https://doi.org/10.1007/s10107-016-1096-1"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10107-016-1096-1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032110827", 
              "https://doi.org/10.1007/s10107-016-1096-1"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/285055.285059", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037698707"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.dam.2013.05.035", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1039909411"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1002/net.10053", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1041037499"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10479-005-2043-3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1042785259", 
              "https://doi.org/10.1007/s10479-005-2043-3"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10479-005-2043-3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1042785259", 
              "https://doi.org/10.1007/s10479-005-2043-3"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10479-005-2043-3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1042785259", 
              "https://doi.org/10.1007/s10479-005-2043-3"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0167-6377(02)00121-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1043645163"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10107-003-0396-4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1045733404", 
              "https://doi.org/10.1007/s10107-003-0396-4"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.jcss.2004.04.011", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1046501207"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.cor.2010.07.018", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1046534893"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10107-004-0547-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1047862520", 
              "https://doi.org/10.1007/s10107-004-0547-2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10107-004-0547-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1047862520", 
              "https://doi.org/10.1007/s10107-004-0547-2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.orl.2004.11.005", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1048435536"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0166-218x(79)90044-1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1050120857"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/276698.276725", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1053745830"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/050641661", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062846595"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/130938645", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062871318"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/s0097539701398594", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062879342"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/s0097539702416402", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062879407"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/s0097539792224474", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062879702"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1214/14-aos1223", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1064394624"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1287/ijoc.1080.0280", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1064706696"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1287/ijoc.11.3.217", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1064706812"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1287/moor.10.2.180", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1064722675"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/2981561", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1084227887"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/sfcs.1996.548477", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1093724804"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/focs.2008.62", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1094994649"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2018-03-16", 
        "datePublishedReg": "2018-03-16", 
        "description": "In the last two decades, a steady stream of research has been devoted to studying various computational aspects of the ordered k-median problem, which subsumes traditional facility location problems (such as median, center, p-centrum, etc.) through a unified modeling approach. Given a finite metric space, the objective is to locate k facilities in order to minimize the ordered median cost function. In its general form, this function penalizes the coverage distance of each vertex by a multiplicative weight, depending on its ranking (or percentile) in the ordered list of all coverage distances. While antecedent literature has focused on mathematical properties of ordered median functions, integer programming methods, various heuristics, and special cases, this problem was not studied thus far through the lens of approximation algorithms. In particular, even on simple network topologies, such as trees or line graphs, obtaining non-trivial approximation guarantees is an open question. The main contribution of this paper is to devise the first provably-good approximation algorithms for the ordered k-median problem. We develop a novel approach that relies primarily on a surrogate model, where the ordered median function is replaced by a simplified ranking-invariant functional form, via efficient enumeration. Surprisingly, while this surrogate model is \u03a9(n\u03a9(1))-hard to approximate on general metrics, we obtain an O(logn)-approximation for our original problem by employing local search methods on a smooth variant of the surrogate function. In addition, an improved guarantee of 2+\u03f5 is obtained on tree metrics by optimally solving the surrogate model through dynamic programming. Finally, we show that the latter optimality gap is tight up to an O(\u03f5) term.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/s10107-018-1259-3", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1047630", 
            "issn": [
              "0025-5610", 
              "1436-4646"
            ], 
            "name": "Mathematical Programming", 
            "type": "Periodical"
          }
        ], 
        "name": "The ordered k-median problem: surrogate models and approximation algorithms", 
        "pagination": "1-29", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "9b32cb1f8cb3efd58909ae4f8ba3092d475b6768b667c90c43dc6fc4cb8789fc"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s10107-018-1259-3"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1101553316"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s10107-018-1259-3", 
          "https://app.dimensions.ai/details/publication/pub.1101553316"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-11T11:55", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000359_0000000359/records_29204_00000003.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://link.springer.com/10.1007%2Fs10107-018-1259-3"
      }
    ]
     

    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/s10107-018-1259-3'

    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/s10107-018-1259-3'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s10107-018-1259-3'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s10107-018-1259-3'


     

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

    213 TRIPLES      21 PREDICATES      70 URIs      16 LITERALS      5 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s10107-018-1259-3 schema:about anzsrc-for:01
    2 anzsrc-for:0102
    3 schema:author Nac617eb4e2a54782bf429afe0a98530d
    4 schema:citation sg:pub.10.1007/978-3-319-13111-5
    5 sg:pub.10.1007/978-3-642-56656-1_12
    6 sg:pub.10.1007/bf02578990
    7 sg:pub.10.1007/s00493-010-2302-z
    8 sg:pub.10.1007/s10107-003-0396-4
    9 sg:pub.10.1007/s10107-004-0547-2
    10 sg:pub.10.1007/s10107-016-1096-1
    11 sg:pub.10.1007/s10479-005-2043-3
    12 sg:pub.10.1007/s10878-010-9353-3
    13 sg:pub.10.1007/s10898-008-9326-6
    14 https://doi.org/10.1002/(sici)1097-0037(199812)32:4<255::aid-net2>3.0.co;2-o
    15 https://doi.org/10.1002/(sici)1097-0037(199912)34:4<283::aid-net8>3.0.co;2-2
    16 https://doi.org/10.1002/net.10053
    17 https://doi.org/10.1006/jagm.2000.1100
    18 https://doi.org/10.1016/0020-0190(92)90208-d
    19 https://doi.org/10.1016/0166-218x(79)90044-1
    20 https://doi.org/10.1016/j.cor.2005.03.025
    21 https://doi.org/10.1016/j.cor.2008.08.019
    22 https://doi.org/10.1016/j.cor.2010.07.018
    23 https://doi.org/10.1016/j.dam.2013.05.035
    24 https://doi.org/10.1016/j.ejor.2006.09.069
    25 https://doi.org/10.1016/j.ejor.2008.02.033
    26 https://doi.org/10.1016/j.ejor.2013.09.029
    27 https://doi.org/10.1016/j.ejor.2016.10.016
    28 https://doi.org/10.1016/j.jcss.2004.04.011
    29 https://doi.org/10.1016/j.orl.2004.11.005
    30 https://doi.org/10.1016/s0166-218x(00)00253-5
    31 https://doi.org/10.1016/s0167-6377(02)00121-9
    32 https://doi.org/10.1109/focs.2008.62
    33 https://doi.org/10.1109/sfcs.1996.548477
    34 https://doi.org/10.1137/050641661
    35 https://doi.org/10.1137/130938645
    36 https://doi.org/10.1137/s0097539701398594
    37 https://doi.org/10.1137/s0097539702416402
    38 https://doi.org/10.1137/s0097539792224474
    39 https://doi.org/10.1145/276698.276725
    40 https://doi.org/10.1145/285055.285059
    41 https://doi.org/10.1145/2981561
    42 https://doi.org/10.1145/301250.301257
    43 https://doi.org/10.1145/375827.375845
    44 https://doi.org/10.1145/509907.510012
    45 https://doi.org/10.1177/0160017612450710
    46 https://doi.org/10.1214/14-aos1223
    47 https://doi.org/10.1287/ijoc.1080.0280
    48 https://doi.org/10.1287/ijoc.11.3.217
    49 https://doi.org/10.1287/moor.10.2.180
    50 schema:datePublished 2018-03-16
    51 schema:datePublishedReg 2018-03-16
    52 schema:description In the last two decades, a steady stream of research has been devoted to studying various computational aspects of the ordered k-median problem, which subsumes traditional facility location problems (such as median, center, p-centrum, etc.) through a unified modeling approach. Given a finite metric space, the objective is to locate k facilities in order to minimize the ordered median cost function. In its general form, this function penalizes the coverage distance of each vertex by a multiplicative weight, depending on its ranking (or percentile) in the ordered list of all coverage distances. While antecedent literature has focused on mathematical properties of ordered median functions, integer programming methods, various heuristics, and special cases, this problem was not studied thus far through the lens of approximation algorithms. In particular, even on simple network topologies, such as trees or line graphs, obtaining non-trivial approximation guarantees is an open question. The main contribution of this paper is to devise the first provably-good approximation algorithms for the ordered k-median problem. We develop a novel approach that relies primarily on a surrogate model, where the ordered median function is replaced by a simplified ranking-invariant functional form, via efficient enumeration. Surprisingly, while this surrogate model is Ω(nΩ(1))-hard to approximate on general metrics, we obtain an O(logn)-approximation for our original problem by employing local search methods on a smooth variant of the surrogate function. In addition, an improved guarantee of 2+ϵ is obtained on tree metrics by optimally solving the surrogate model through dynamic programming. Finally, we show that the latter optimality gap is tight up to an O(ϵ) term.
    53 schema:genre research_article
    54 schema:inLanguage en
    55 schema:isAccessibleForFree false
    56 schema:isPartOf sg:journal.1047630
    57 schema:name The ordered k-median problem: surrogate models and approximation algorithms
    58 schema:pagination 1-29
    59 schema:productId N03f01630ba1743d587f42ddfaab2ab1d
    60 N7103e891a6c9453e999cb1db2dd133a9
    61 Nb53e8d98af794443a7ad5d1855859e4a
    62 schema:sameAs https://app.dimensions.ai/details/publication/pub.1101553316
    63 https://doi.org/10.1007/s10107-018-1259-3
    64 schema:sdDatePublished 2019-04-11T11:55
    65 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    66 schema:sdPublisher Nafab11110b7f468c8a0e5fb455bb06ba
    67 schema:url https://link.springer.com/10.1007%2Fs10107-018-1259-3
    68 sgo:license sg:explorer/license/
    69 sgo:sdDataset articles
    70 rdf:type schema:ScholarlyArticle
    71 N03f01630ba1743d587f42ddfaab2ab1d schema:name readcube_id
    72 schema:value 9b32cb1f8cb3efd58909ae4f8ba3092d475b6768b667c90c43dc6fc4cb8789fc
    73 rdf:type schema:PropertyValue
    74 N260aae7c74dd49b79a4c0ef1f72bf4b0 rdf:first sg:person.016117407141.65
    75 rdf:rest rdf:nil
    76 N7103e891a6c9453e999cb1db2dd133a9 schema:name doi
    77 schema:value 10.1007/s10107-018-1259-3
    78 rdf:type schema:PropertyValue
    79 Nac617eb4e2a54782bf429afe0a98530d rdf:first sg:person.010255531614.72
    80 rdf:rest N260aae7c74dd49b79a4c0ef1f72bf4b0
    81 Nafab11110b7f468c8a0e5fb455bb06ba schema:name Springer Nature - SN SciGraph project
    82 rdf:type schema:Organization
    83 Nb53e8d98af794443a7ad5d1855859e4a schema:name dimensions_id
    84 schema:value pub.1101553316
    85 rdf:type schema:PropertyValue
    86 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    87 schema:name Mathematical Sciences
    88 rdf:type schema:DefinedTerm
    89 anzsrc-for:0102 schema:inDefinedTermSet anzsrc-for:
    90 schema:name Applied Mathematics
    91 rdf:type schema:DefinedTerm
    92 sg:journal.1047630 schema:issn 0025-5610
    93 1436-4646
    94 schema:name Mathematical Programming
    95 rdf:type schema:Periodical
    96 sg:person.010255531614.72 schema:affiliation https://www.grid.ac/institutes/grid.14868.33
    97 schema:familyName Aouad
    98 schema:givenName Ali
    99 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010255531614.72
    100 rdf:type schema:Person
    101 sg:person.016117407141.65 schema:affiliation https://www.grid.ac/institutes/grid.18098.38
    102 schema:familyName Segev
    103 schema:givenName Danny
    104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016117407141.65
    105 rdf:type schema:Person
    106 sg:pub.10.1007/978-3-319-13111-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006415661
    107 https://doi.org/10.1007/978-3-319-13111-5
    108 rdf:type schema:CreativeWork
    109 sg:pub.10.1007/978-3-642-56656-1_12 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006992019
    110 https://doi.org/10.1007/978-3-642-56656-1_12
    111 rdf:type schema:CreativeWork
    112 sg:pub.10.1007/bf02578990 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004867366
    113 https://doi.org/10.1007/bf02578990
    114 rdf:type schema:CreativeWork
    115 sg:pub.10.1007/s00493-010-2302-z schema:sameAs https://app.dimensions.ai/details/publication/pub.1021005060
    116 https://doi.org/10.1007/s00493-010-2302-z
    117 rdf:type schema:CreativeWork
    118 sg:pub.10.1007/s10107-003-0396-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045733404
    119 https://doi.org/10.1007/s10107-003-0396-4
    120 rdf:type schema:CreativeWork
    121 sg:pub.10.1007/s10107-004-0547-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047862520
    122 https://doi.org/10.1007/s10107-004-0547-2
    123 rdf:type schema:CreativeWork
    124 sg:pub.10.1007/s10107-016-1096-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032110827
    125 https://doi.org/10.1007/s10107-016-1096-1
    126 rdf:type schema:CreativeWork
    127 sg:pub.10.1007/s10479-005-2043-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042785259
    128 https://doi.org/10.1007/s10479-005-2043-3
    129 rdf:type schema:CreativeWork
    130 sg:pub.10.1007/s10878-010-9353-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024266334
    131 https://doi.org/10.1007/s10878-010-9353-3
    132 rdf:type schema:CreativeWork
    133 sg:pub.10.1007/s10898-008-9326-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027809022
    134 https://doi.org/10.1007/s10898-008-9326-6
    135 rdf:type schema:CreativeWork
    136 https://doi.org/10.1002/(sici)1097-0037(199812)32:4<255::aid-net2>3.0.co;2-o schema:sameAs https://app.dimensions.ai/details/publication/pub.1020119512
    137 rdf:type schema:CreativeWork
    138 https://doi.org/10.1002/(sici)1097-0037(199912)34:4<283::aid-net8>3.0.co;2-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006604005
    139 rdf:type schema:CreativeWork
    140 https://doi.org/10.1002/net.10053 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041037499
    141 rdf:type schema:CreativeWork
    142 https://doi.org/10.1006/jagm.2000.1100 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019452982
    143 rdf:type schema:CreativeWork
    144 https://doi.org/10.1016/0020-0190(92)90208-d schema:sameAs https://app.dimensions.ai/details/publication/pub.1029425565
    145 rdf:type schema:CreativeWork
    146 https://doi.org/10.1016/0166-218x(79)90044-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050120857
    147 rdf:type schema:CreativeWork
    148 https://doi.org/10.1016/j.cor.2005.03.025 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018119569
    149 rdf:type schema:CreativeWork
    150 https://doi.org/10.1016/j.cor.2008.08.019 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012000925
    151 rdf:type schema:CreativeWork
    152 https://doi.org/10.1016/j.cor.2010.07.018 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046534893
    153 rdf:type schema:CreativeWork
    154 https://doi.org/10.1016/j.dam.2013.05.035 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039909411
    155 rdf:type schema:CreativeWork
    156 https://doi.org/10.1016/j.ejor.2006.09.069 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010447297
    157 rdf:type schema:CreativeWork
    158 https://doi.org/10.1016/j.ejor.2008.02.033 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009793253
    159 rdf:type schema:CreativeWork
    160 https://doi.org/10.1016/j.ejor.2013.09.029 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023113952
    161 rdf:type schema:CreativeWork
    162 https://doi.org/10.1016/j.ejor.2016.10.016 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010660638
    163 rdf:type schema:CreativeWork
    164 https://doi.org/10.1016/j.jcss.2004.04.011 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046501207
    165 rdf:type schema:CreativeWork
    166 https://doi.org/10.1016/j.orl.2004.11.005 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048435536
    167 rdf:type schema:CreativeWork
    168 https://doi.org/10.1016/s0166-218x(00)00253-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026610330
    169 rdf:type schema:CreativeWork
    170 https://doi.org/10.1016/s0167-6377(02)00121-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043645163
    171 rdf:type schema:CreativeWork
    172 https://doi.org/10.1109/focs.2008.62 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094994649
    173 rdf:type schema:CreativeWork
    174 https://doi.org/10.1109/sfcs.1996.548477 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093724804
    175 rdf:type schema:CreativeWork
    176 https://doi.org/10.1137/050641661 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062846595
    177 rdf:type schema:CreativeWork
    178 https://doi.org/10.1137/130938645 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062871318
    179 rdf:type schema:CreativeWork
    180 https://doi.org/10.1137/s0097539701398594 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062879342
    181 rdf:type schema:CreativeWork
    182 https://doi.org/10.1137/s0097539702416402 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062879407
    183 rdf:type schema:CreativeWork
    184 https://doi.org/10.1137/s0097539792224474 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062879702
    185 rdf:type schema:CreativeWork
    186 https://doi.org/10.1145/276698.276725 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053745830
    187 rdf:type schema:CreativeWork
    188 https://doi.org/10.1145/285055.285059 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037698707
    189 rdf:type schema:CreativeWork
    190 https://doi.org/10.1145/2981561 schema:sameAs https://app.dimensions.ai/details/publication/pub.1084227887
    191 rdf:type schema:CreativeWork
    192 https://doi.org/10.1145/301250.301257 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006383282
    193 rdf:type schema:CreativeWork
    194 https://doi.org/10.1145/375827.375845 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028995883
    195 rdf:type schema:CreativeWork
    196 https://doi.org/10.1145/509907.510012 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001857295
    197 rdf:type schema:CreativeWork
    198 https://doi.org/10.1177/0160017612450710 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026839070
    199 rdf:type schema:CreativeWork
    200 https://doi.org/10.1214/14-aos1223 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064394624
    201 rdf:type schema:CreativeWork
    202 https://doi.org/10.1287/ijoc.1080.0280 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064706696
    203 rdf:type schema:CreativeWork
    204 https://doi.org/10.1287/ijoc.11.3.217 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064706812
    205 rdf:type schema:CreativeWork
    206 https://doi.org/10.1287/moor.10.2.180 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064722675
    207 rdf:type schema:CreativeWork
    208 https://www.grid.ac/institutes/grid.14868.33 schema:alternateName London Business School
    209 schema:name London Business School, NW1 4SA, London, UK
    210 rdf:type schema:Organization
    211 https://www.grid.ac/institutes/grid.18098.38 schema:alternateName University of Haifa
    212 schema:name Department of Statistics, University of Haifa, 31905, Haifa, Israel
    213 rdf:type schema:Organization
     




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


    ...