Ontology type: schema:ScholarlyArticle
2018-03-16
AUTHORS ABSTRACTIn 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... »
PAGES1-29
http://scigraph.springernature.com/pub.10.1007/s10107-018-1259-3
DOIhttp://dx.doi.org/10.1007/s10107-018-1259-3
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1101553316
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
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