Publikation: Mind the Gap : Edge Facility Location Problems in Theory and Practice
Dateien
Datum
Autor:innen
Herausgeber:innen
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
DOI (zitierfähiger Link)
Internationale Patentnummer
Angaben zur Forschungsförderung
Projekt
Open Access-Veröffentlichung
Core Facility der Universität Konstanz
Titel in einer weiteren Sprache
Publikationstyp
Publikationsstatus
Erschienen in
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)
Schlagwörter
Konferenz
Rezension
Zitieren
ISO 690
BECK, 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_25BibTex
@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>