Publikation:

Mind the Gap : Edge Facility Location Problems in Theory and Practice

Lade...
Vorschaubild

Dateien

Zu diesem Dokument gibt es keine Dateien.

Datum

2023

Autor:innen

Herausgeber:innen

Kontakt

ISSN der Zeitschrift

Electronic ISSN

ISBN

Bibliografische Daten

Verlag

Schriftenreihe

Auflagebezeichnung

URI (zitierfähiger Link)
ArXiv-ID

Internationale Patentnummer

Angaben zur Forschungsförderung

Projekt

Open Access-Veröffentlichung
Core Facility der Universität Konstanz

Gesperrt bis

Titel in einer weiteren Sprache

Publikationstyp
Beitrag zu einem Konferenzband
Publikationsstatus
Published

Erschienen in

BAGCHI, Amitabha, ed., Rahul MUTHU, ed.. Algorithms and Discrete Applied Mathematics : 9th International Conference, CALDAM 2023, Gandhinagar, India, February 9-11, 2023, Proceedings. Cham: Springer, 2023, pp. 321-334. Lecture Notes in Computer Science. 13947. ISSN 0302-9743. eISSN 1611-3349. ISBN 978-3-031-25210-5. Available under: doi: 10.1007/978-3-031-25211-2_25

Zusammenfassung

Motivated by applications in urban planning, network analysis, and data visualization, we introduce center selection problems in graphs where the centers are represented by edges. This is in contrast to classic center selection problems where centers are usually placed at the nodes of a graph. Given a weighted graph G(V, E) and a budget k∈N, the goal is to select k edges from E such that the maximum distance from any point of interest in the graph to its nearest center is minimized. We consider three different problem variants, based on defining the points of interest either as the edges of G, or the nodes, or all points on the edges. We provide a variety of hardness results and approximation algorithms. A key difficulty of edge center selection is that the underlying distance function may not satisfy the triangle inequality, which is crucially used in approximation algorithms for node center selection. In addition, we introduce efficient heuristics that produce solutions of good quality even in large graphs, as demonstrated in our experimental evaluation.

Zusammenfassung in einer weiteren Sprache

Fachgebiet (DDC)
004 Informatik

Schlagwörter

Facility location, Edge facility, K-center

Konferenz

CALDAM 2023 : 9th International Conference on Algorithms and Discrete Applied Mathematics, 9. Feb. 2023 - 11. Feb. 2023, Gandhinagar, India
Rezension
undefined / . - undefined, undefined

Forschungsvorhaben

Organisationseinheiten

Zeitschriftenheft

Zugehörige Datensätze in KOPS

Zitieren

ISO 690BECK, Moritz, Joachim SPOERHASE, Sabine STORANDT, 2023. Mind the Gap : Edge Facility Location Problems in Theory and Practice. CALDAM 2023 : 9th International Conference on Algorithms and Discrete Applied Mathematics. Gandhinagar, India, 9. Feb. 2023 - 11. Feb. 2023. In: BAGCHI, Amitabha, ed., Rahul MUTHU, ed.. Algorithms and Discrete Applied Mathematics : 9th International Conference, CALDAM 2023, Gandhinagar, India, February 9-11, 2023, Proceedings. Cham: Springer, 2023, pp. 321-334. Lecture Notes in Computer Science. 13947. ISSN 0302-9743. eISSN 1611-3349. ISBN 978-3-031-25210-5. Available under: doi: 10.1007/978-3-031-25211-2_25
BibTex
@inproceedings{Beck2023Facil-66134,
  year={2023},
  doi={10.1007/978-3-031-25211-2_25},
  title={Mind the Gap : Edge Facility Location Problems in Theory and Practice},
  number={13947},
  isbn={978-3-031-25210-5},
  issn={0302-9743},
  publisher={Springer},
  address={Cham},
  series={Lecture Notes in Computer Science},
  booktitle={Algorithms and Discrete Applied Mathematics : 9th International Conference, CALDAM 2023, Gandhinagar, India, February 9-11, 2023, Proceedings},
  pages={321--334},
  editor={Bagchi, Amitabha and Muthu, Rahul},
  author={Beck, Moritz and Spoerhase, Joachim and Storandt, Sabine}
}
RDF
<rdf:RDF
    xmlns:dcterms="http://purl.org/dc/terms/"
    xmlns:dc="http://purl.org/dc/elements/1.1/"
    xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
    xmlns:bibo="http://purl.org/ontology/bibo/"
    xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#"
    xmlns:foaf="http://xmlns.com/foaf/0.1/"
    xmlns:void="http://rdfs.org/ns/void#"
    xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > 
  <rdf:Description rdf:about="https://kops.uni-konstanz.de/server/rdf/resource/123456789/66134">
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2023-02-20T12:25:06Z</dcterms:available>
    <dc:contributor>Spoerhase, Joachim</dc:contributor>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dc:contributor>Beck, Moritz</dc:contributor>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:contributor>Storandt, Sabine</dc:contributor>
    <dc:creator>Spoerhase, Joachim</dc:creator>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dcterms:abstract>Motivated by applications in urban planning, network analysis, and data visualization, we introduce center selection problems in graphs where the centers are represented by edges. This is in contrast to classic center selection problems where centers are usually placed at the nodes of a graph. Given a weighted graph G(V, E) and a budget k∈N, the goal is to select k edges from E such that the maximum distance from any point of interest in the graph to its nearest center is minimized. We consider three different problem variants, based on defining the points of interest either as the edges of G, or the nodes, or all points on the edges. We provide a variety of hardness results and approximation algorithms. A key difficulty of edge center selection is that the underlying distance function may not satisfy the triangle inequality, which is crucially used in approximation algorithms for node center selection. In addition, we introduce efficient heuristics that produce solutions of good quality even in large graphs, as demonstrated in our experimental evaluation.</dcterms:abstract>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2023-02-20T12:25:06Z</dc:date>
    <dcterms:issued>2023</dcterms:issued>
    <dc:language>eng</dc:language>
    <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/66134"/>
    <dc:creator>Storandt, Sabine</dc:creator>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:creator>Beck, Moritz</dc:creator>
    <dcterms:title>Mind the Gap : Edge Facility Location Problems in Theory and Practice</dcterms:title>
  </rdf:Description>
</rdf:RDF>

Interner Vermerk

xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter

Kontakt
URL der Originalveröffentl.

Prüfdatum der URL

Prüfungsdatum der Dissertation

Finanzierungsart

Kommentar zur Publikation

Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Ja
Begutachtet
Diese Publikation teilen