2 Search Results for "Leitner, Michael"

Document
DOI: 10.4230/LIPIcs.ESA.2024.41
Approximation Algorithms for Hop Constrained and Buy-At-Bulk Network Design via Hop Constrained Oblivious Routing

Authors: Chandra Chekuri and Rhea Jain

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
We consider two-cost network design models in which edges of the input graph have an associated cost and length. We build upon recent advances in hop-constrained oblivious routing to obtain two sets of results. We address multicommodity buy-at-bulk network design in the nonuniform setting. Existing poly-logarithmic approximations are based on the junction tree approach [Chekuri et al., 2010; Guy Kortsarz and Zeev Nutov, 2011]. We obtain a new polylogarithmic approximation via a natural LP relaxation. This establishes an upper bound on its integrality gap and affirmatively answers an open question raised in [Chekuri et al., 2010]. The rounding is based on recent results in hop-constrained oblivious routing [Ghaffari et al., 2021], and this technique yields a polylogarithmic approximation in more general settings such as set connectivity. Our algorithm for buy-at-bulk network design is based on an LP-based reduction to h-hop constrained network design for which we obtain LP-based bicriteria approximation algorithms. We also consider a fault-tolerant version of h-hop constrained network design where one wants to design a low-cost network to guarantee short paths between a given set of source-sink pairs even when k-1 edges can fail. This model has been considered in network design [Luis Gouveia and Markus Leitner, 2017; Gouveia et al., 2018; Arslan et al., 2020] but no approximation algorithms were known. We obtain polylogarithmic bicriteria approximation algorithms for the single-source setting for any fixed k. We build upon the single-source algorithm and the junction-tree approach to obtain an approximation algorithm for the multicommodity setting when at most one edge can fail.
Cite as

Chandra Chekuri and Rhea Jain. Approximation Algorithms for Hop Constrained and Buy-At-Bulk Network Design via Hop Constrained Oblivious Routing. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 41:1-41:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chekuri_et_al:LIPIcs.ESA.2024.41,
  author =	{Chekuri, Chandra and Jain, Rhea},
  title =	{{Approximation Algorithms for Hop Constrained and Buy-At-Bulk Network Design via Hop Constrained Oblivious Routing}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{41:1--41:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.41},
  URN =		{urn:nbn:de:0030-drops-211124},
  doi =		{10.4230/LIPIcs.ESA.2024.41},
  annote =	{Keywords: Buy-at-bulk, Hop-constrained network design, LP integrality gap, Fault-tolerant network design}
}
Document
Short Paper
DOI: 10.4230/LIPIcs.GISCIENCE.2018.56
Geosocial Media Data as Predictors in a GWR Application to Forecast Crime Hotspots (Short Paper)

Authors: Alina Ristea, Ourania Kounadi, and Michael Leitner

Published in: LIPIcs, Volume 114, 10th International Conference on Geographic Information Science (GIScience 2018)

Abstract
In this paper we forecast hotspots of street crime in Portland, Oregon. Our approach uses geosocial media posts, which define the predictors in geographically weighted regression (GWR) models. We use two predictors that are both derived from Twitter data. The first one is the population at risk of being victim of street crime. The second one is the crime related tweets. These two predictors were used in GWR to create models that depict future street crime hotspots. The predicted hotspots enclosed more than 23% of the future street crimes in 1% of the study area and also outperformed the prediction efficiency of a baseline approach. Future work will focus on optimizing the prediction parameters and testing the applicability of this approach to other mobile crime types.
Cite as

Alina Ristea, Ourania Kounadi, and Michael Leitner. Geosocial Media Data as Predictors in a GWR Application to Forecast Crime Hotspots (Short Paper). In 10th International Conference on Geographic Information Science (GIScience 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 114, pp. 56:1-56:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{ristea_et_al:LIPIcs.GISCIENCE.2018.56,
  author =	{Ristea, Alina and Kounadi, Ourania and Leitner, Michael},
  title =	{{Geosocial Media Data as Predictors in a GWR Application to Forecast Crime Hotspots}},
  booktitle =	{10th International Conference on Geographic Information Science (GIScience 2018)},
  pages =	{56:1--56:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-083-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{114},
  editor =	{Winter, Stephan and Griffin, Amy and Sester, Monika},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GISCIENCE.2018.56},
  URN =		{urn:nbn:de:0030-drops-93845},
  doi =		{10.4230/LIPIcs.GISCIENCE.2018.56},
  annote =	{Keywords: spatial crime prediction, street crime, population at risk, geographically weighted regression, geosocial media}
}
  • Refine by Author
  • 1 Chekuri, Chandra
  • 1 Jain, Rhea
  • 1 Kounadi, Ourania
  • 1 Leitner, Michael
  • 1 Ristea, Alina

  • Refine by Classification
  • 1 Information systems → Geographic information systems
  • 1 Theory of computation → Discrete optimization
  • 1 Theory of computation → Routing and network design problems

  • Refine by Keyword
  • 1 Buy-at-bulk
  • 1 Fault-tolerant network design
  • 1 Hop-constrained network design
  • 1 LP integrality gap
  • 1 geographically weighted regression
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2018
  • 1 2024

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact