Search Results

Documents authored by Bhattacharya, Binay

Document
DOI: 10.4230/OASIcs.ATMOS.2021.13
Locating Evacuation Centers Optimally in Path and Cycle Networks

Authors: Robert Benkoczi, Binay Bhattacharya, Yuya Higashikawa, Tsunehiko Kameda, Naoki Katoh, and Junichi Teruyama

Published in: OASIcs, Volume 96, 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)

Abstract
We present dynamic flow algorithms to solve the k-sink problem whose aim is to locate k sinks (evacuation centers) in such a way that the evacuation time of the last evacuee is minimized. In the confluent model, the evacuees originating from or passing through a vertex must evacuate to the same sink, and most known results on the k-sink problem adopt the confluent model. When the edge capacities are uniform (resp. general), our algorithms for non-confluent flow in the path networks run in O(n + k² log² n) (resp. O(n log(n) + k² log⁵ n)) time, where n is the number of vertices. Our algorithms for cycle networks run in O(k²n log² n) (resp. O(k²n log⁵ n)) time, when the edge capacities are uniform (resp. general).
Cite as

Robert Benkoczi, Binay Bhattacharya, Yuya Higashikawa, Tsunehiko Kameda, Naoki Katoh, and Junichi Teruyama. Locating Evacuation Centers Optimally in Path and Cycle Networks. In 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021). Open Access Series in Informatics (OASIcs), Volume 96, pp. 13:1-13:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{benkoczi_et_al:OASIcs.ATMOS.2021.13,
  author =	{Benkoczi, Robert and Bhattacharya, Binay and Higashikawa, Yuya and Kameda, Tsunehiko and Katoh, Naoki and Teruyama, Junichi},
  title =	{{Locating Evacuation Centers Optimally in Path and Cycle Networks}},
  booktitle =	{21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)},
  pages =	{13:1--13:19},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-213-6},
  ISSN =	{2190-6807},
  year =	{2021},
  volume =	{96},
  editor =	{M\"{u}ller-Hannemann, Matthias and Perea, Federico},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2021.13},
  URN =		{urn:nbn:de:0030-drops-148825},
  doi =		{10.4230/OASIcs.ATMOS.2021.13},
  annote =	{Keywords: Efficient algorithms, facility location, minmax sink, evacuation problem, dynamic flow in network}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2019.27
The Weighted k-Center Problem in Trees for Fixed k

Authors: Binay Bhattacharya, Sandip Das, and Subhadeep Ranjan Dev

Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)

Abstract
We present a linear time algorithm for the weighted k-center problem on trees for fixed k. This partially settles the long-standing question about the lower bound on the time complexity of the problem. The current time complexity of the best-known algorithm for the problem with k as part of the input is O(n log n) by Wang et al. [Haitao Wang and Jingru Zhang, 2018]. Whether an O(n) time algorithm exists for arbitrary k is still open.
Cite as

Binay Bhattacharya, Sandip Das, and Subhadeep Ranjan Dev. The Weighted k-Center Problem in Trees for Fixed k. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 27:1-27:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{bhattacharya_et_al:LIPIcs.ISAAC.2019.27,
  author =	{Bhattacharya, Binay and Das, Sandip and Dev, Subhadeep Ranjan},
  title =	{{The Weighted k-Center Problem in Trees for Fixed k}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{27:1--27:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Lu, Pinyan and Zhang, Guochuan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.27},
  URN =		{urn:nbn:de:0030-drops-115238},
  doi =		{10.4230/LIPIcs.ISAAC.2019.27},
  annote =	{Keywords: facility location, prune and search, parametric search, k-center problem, conditional k-center problem, trees}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2018.14
An O(n^2 log^2 n) Time Algorithm for Minmax Regret Minsum Sink on Path Networks

Authors: Binay Bhattacharya, Yuya Higashikawa, Tsunehiko Kameda, and Naoki Katoh

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
We model evacuation in emergency situations by dynamic flow in a network. We want to minimize the aggregate evacuation time to an evacuation center (called a sink) on a path network with uniform edge capacities. The evacuees are initially located at the vertices, but their precise numbers are unknown, and are given by upper and lower bounds. Under this assumption, we compute a sink location that minimizes the maximum "regret." We present the first sub-cubic time algorithm in n to solve this problem, where n is the number of vertices. Although we cast our problem as evacuation, our result is accurate if the "evacuees" are fluid-like continuous material, but is a good approximation for discrete evacuees.
Cite as

Binay Bhattacharya, Yuya Higashikawa, Tsunehiko Kameda, and Naoki Katoh. An O(n^2 log^2 n) Time Algorithm for Minmax Regret Minsum Sink on Path Networks. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 14:1-14:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bhattacharya_et_al:LIPIcs.ISAAC.2018.14,
  author =	{Bhattacharya, Binay and Higashikawa, Yuya and Kameda, Tsunehiko and Katoh, Naoki},
  title =	{{An O(n^2 log^2 n) Time Algorithm for Minmax Regret Minsum Sink on Path Networks}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{14:1--14:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.14},
  URN =		{urn:nbn:de:0030-drops-99624},
  doi =		{10.4230/LIPIcs.ISAAC.2018.14},
  annote =	{Keywords: Facility location, minsum sink, evacuation problem, minmax regret, dynamic flow path network}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2016.6
The p-Center Problem in Tree Networks Revisited

Authors: Aritra Banik, Binay Bhattacharya, Sandip Das, Tsunehiko Kameda, and Zhao Song

Published in: LIPIcs, Volume 53, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)

Abstract
We present two improved algorithms for weighted discrete p-center problem for tree networks with n vertices. One of our proposed algorithms runs in O(n*log(n) + p*log^2(n) * log(n/p)) time. For all values of p, our algorithm thus runs as fast as or faster than the most efficient O(n*log^2(n)) time algorithm obtained by applying Cole's [1987] speed-up technique to the algorithm due to Megiddo and Tamir [1983], which has remained unchallenged for nearly 30 years. Our other algorithm, which is more practical, runs in O(n*log(n) + p^2*log^2(n/p)) time, and when p=O(sqrt(n)) it is faster than Megiddo and Tamir's O(n*log^2(n) * log(log(n))) time algorithm [1983].
Cite as

Aritra Banik, Binay Bhattacharya, Sandip Das, Tsunehiko Kameda, and Zhao Song. The p-Center Problem in Tree Networks Revisited. In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 53, pp. 6:1-6:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{banik_et_al:LIPIcs.SWAT.2016.6,
  author =	{Banik, Aritra and Bhattacharya, Binay and Das, Sandip and Kameda, Tsunehiko and Song, Zhao},
  title =	{{The p-Center Problem in Tree Networks Revisited}},
  booktitle =	{15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)},
  pages =	{6:1--6:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-011-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{53},
  editor =	{Pagh, Rasmus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2016.6},
  URN =		{urn:nbn:de:0030-drops-60296},
  doi =		{10.4230/LIPIcs.SWAT.2016.6},
  annote =	{Keywords: Facility location, p-center, parametric search, tree network, sorting network}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2012.325
k-delivery traveling salesman problem on tree networks

Authors: Binay Bhattacharya and Yuzhuang Hu

Published in: LIPIcs, Volume 18, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)

Abstract
In this paper we study the k-delivery traveling salesman problem (TSP)on trees, a variant of the non-preemptive capacitated vehicle routing problem with pickups and deliveries. We are given n pickup locations and n delivery locations on trees, with exactly one item at each pickup location. The k-delivery TSP is to find a minimum length tour by a vehicle of finite capacity k to pick up and deliver exactly one item to each delivery location. We show that an optimal solution for the k-delivery TSP on paths can be found that allows succinct representations of the routes. By exploring the symmetry inherent in the k-delivery TSP, we design a 5/3-approximation algorithm for the k-delivery TSP on trees of arbitrary heights. The ratio can be improved to (3/2 - 1/2k) for the problem on trees of height 2. The developed algorithms are based on the following observation: under certain conditions, it makes sense for a non-empty vehicle to turn around and pick up additional loads.
Cite as

Binay Bhattacharya and Yuzhuang Hu. k-delivery traveling salesman problem on tree networks. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 18, pp. 325-336, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{bhattacharya_et_al:LIPIcs.FSTTCS.2012.325,
  author =	{Bhattacharya, Binay and Hu, Yuzhuang},
  title =	{{k-delivery traveling salesman problem on tree networks}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)},
  pages =	{325--336},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-47-7},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{18},
  editor =	{D'Souza, Deepak and Radhakrishnan, Jaikumar and Telikepalli, Kavitha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2012.325},
  URN =		{urn:nbn:de:0030-drops-38707},
  doi =		{10.4230/LIPIcs.FSTTCS.2012.325},
  annote =	{Keywords: k-delivery traveling salesman problem, approximation algorithms}
}
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 About DROPS Imprint Privacy Contact