DROPS

Document

DOI: 10.4230/OASIcs.ATMOS.2023.10

Submodularity Property for Facility Locations of Dynamic Flow Networks

Authors: Peerawit Suriya, Vorapong Suppakitpaisarn, Supanut Chaidee, and Phapaengmueng Sukkasem

Published in: OASIcs, Volume 115, 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)

Abstract

This paper considers facility location problems within dynamic flow networks, shifting the focus from minimizing evacuation time to handling situations with a constrained evacuation timeframe. Our study sets two main goals: 1) Determining a fixed-size set of locations that can maximize the number of evacuees, and 2) Identifying the smallest set of locations capable of accommodating all evacuees within the time constraint. We introduce flow_t(S) to represent the number of evacuees for given locations S within a fixed time limit t. We prove that flow_t functions is a monotone submodular function, which allows us to apply an approximation algorithm specifically designed for maximizing such functions with size restrictions. For the second objective, we implement an approximation algorithm tailored to solving the submodular cover problem. We conduct experiments on the real datasets of Chiang Mai, and demonstrate that the approximation algorithms give solutions which are close to optimal for all of the experiments we have conducted.

Cite as

Peerawit Suriya, Vorapong Suppakitpaisarn, Supanut Chaidee, and Phapaengmueng Sukkasem. Submodularity Property for Facility Locations of Dynamic Flow Networks. In 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023). Open Access Series in Informatics (OASIcs), Volume 115, pp. 10:1-10:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{suriya_et_al:OASIcs.ATMOS.2023.10,
  author =	{Suriya, Peerawit and Suppakitpaisarn, Vorapong and Chaidee, Supanut and Sukkasem, Phapaengmueng},
  title =	{{Submodularity Property for Facility Locations of Dynamic Flow Networks}},
  booktitle =	{23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)},
  pages =	{10:1--10:13},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-302-7},
  ISSN =	{2190-6807},
  year =	{2023},
  volume =	{115},
  editor =	{Frigioni, Daniele and Schiewe, Philine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2023.10},
  URN =		{urn:nbn:de:0030-drops-187711},
  doi =		{10.4230/OASIcs.ATMOS.2023.10},
  annote =	{Keywords: Approximation Algorithms, Dynamic Networks, Facility Location, Submodular Function Optimization}
}

Search Results

Documents authored by Chaidee, Supanut

Submodularity Property for Facility Locations of Dynamic Flow Networks

Abstract

Cite as

Thanks for your feedback!

Could not send message