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
Forschungsvorhaben
Organisationseinheiten
Zeitschriftenheft
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
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