Author name cluster

Binay Bhattacharya

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

9 papers

1 author row

TCS Journal 2025 Journal Article

Improved algorithms for optimal k sink location on path networks

Binay Bhattacharya
Mordecai J. Golin
Yuya Higashikawa
Tsunehiko Kameda
Naoki Katoh

We address the problem of placing k sinks on dynamic-flow path networks with n vertices so as to minimize their maximum evacuation completion time. We develop two different algorithms that, when all edges have the same capacity, run respectively in O ( n + k 2 log 2 ⁡ n ) and O ( n log ⁡ n ) time. When the edge capacities can be different, i. e. , are general, they run respectively in O ( n log ⁡ n + k 2 log 4 ⁡ n ) and O ( n log 3 ⁡ n ) time. These algorithms improve upon the previously most efficient algorithms, which had time complexities O ( k n ) and O ( k n log 2 ⁡ n ), respectively, for the uniform and general edge capacity models. The improvements are achieved by moving from a dynamic programming based approach to a parametric-search based one.

Details DOI

TCS Journal 2022 Journal Article

The weighted k-center problem in trees for fixed k

Binay Bhattacharya
Sandip Das
Subhadeep Ranjan Dev

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. (2018) [20]. Whether an O ( n ) time algorithm exists for arbitrary k is still open.

Details DOI

TCS Journal 2020 Journal Article

Minsum k-sink problem on path networks

Robert Benkoczi
Binay Bhattacharya
Yuya Higashikawa
Tsunehiko Kameda
Naoki Katoh

We consider the problem of locating a set of k sinks on a path network with general edge capacities that minimizes the sum of the evacuation times of all evacuees. We first present an O ( k n log 4 ⁡ n ) time algorithm when the edge capacities are non-uniform, where n is the number of vertices. We then present an O ( k n log 3 ⁡ n ) time algorithm when the edge capacities are uniform. We also present an O ( n log ⁡ n ) time algorithm for the special case where k = 1 and the edge capacities are non-uniform.

Details DOI

TCS Journal 2018 Journal Article

Optimizing squares covering a set of points

Sergey Bereg
Binay Bhattacharya
Sandip Das
Tsunehiko Kameda
Priya Ranjan Sinha Mahapatra
Zhao Song

We investigate three kinds of optimization problems regarding n points in the 2-dimensional plane that need to be enclosed by squares. (1) Find a given number of squares that enclose all the points, minimizing the size of the largest square used. (2) Problem (1) with the additional condition that the center of each enclosing square must lie on one of the two given axis-parallel lines, which are either parallel or perpendicular. (3) Enclose the maximum number of points, using a specified number of squares of a fixed size. We propose different techniques to solve the above problems in cases where squares are axis-parallel or of arbitrary orientation, disjoint or overlapping. All the algorithms we use run in time that is a low-order polynomial in n, and improve upon the previous algorithms, if any.

Details DOI

TCS Journal 2015 Journal Article

Improved algorithms for computing minmax regret sinks on dynamic path and tree networks

Binay Bhattacharya
Tsunehiko Kameda

Suppose that in an emergency, such as an earthquake or fire, a number of people need to be evacuated to a safe “sink” from every vertex of a network. The k-sink problem seeks to minimize the evacuation time of all the evacuees to k sinks. In the minmax regret version of this problem, the exact number of evacuees at each vertex is unknown, but only an interval for a possible number is given. Under the assumption that all edges have the same capacity, we want to minimize the evacuation time in the worst case, where the actual numbers of evacuees are the most unfavorable to the chosen sink locations. We first present an O ( n ) time algorithm for finding the minmax regret 1-sink on a dynamic path network, improving the previously known O ( n log ⁡ n ) algorithms. We then present an O ( n log 4 ⁡ n ) time algorithm for finding the minmax regret 2-sink on a dynamic path network, improving the previously best O ( n 2 log 2 ⁡ n ) time algorithm. We also present an O ( n log ⁡ n ) time algorithm for finding the minmax regret 1-sink in a dynamic tree network, improving the previously best algorithm that runs in O ( n 2 log 2 ⁡ n ) time.

Details DOI

TCS Journal 2014 Journal Article

The cyclical scheduling problem

Binay Bhattacharya
Soudipta Chakraborty
Ehsan Iranmanesh
Ramesh Krishnamurti

We consider the ( n − 2, n ) cyclical scheduling problem which assigns a shift of n − 2 consecutive periods among a total of n periods to workers. We solve this problem by solving a series of b-matching problems on a cycle of n vertices. Each vertex has a capacity, and edges have costs associated with them. The objective is to maximize the total cost of the matching. The best known algorithm for this problem uses network flow, which runs in O ( n 2 log ⁡ n ) on a cycle. We provide an O ( n log ⁡ n ) algorithm for this problem. Using this, we provide an O ( n log ⁡ n log ⁡ n b max ) algorithm for the ( n − 2, n ) cyclical scheduling problem, where b max is the maximum capacity on a vertex.

Details DOI

I&C Journal 2012 Journal Article

Efficient algorithms for the conditional covering problem

Robert Benkoczi
Binay Bhattacharya
Yuzhuang Hu
Chien-Hsin Lin
Qiaosheng Shi
Biing-Feng Wang

We consider the conditional covering problem in an undirected network, in which each vertex represents a demand point that must be covered by a facility as well as a potential facility site. Each facility can cover all vertices within a given coverage radius, except the vertex at which the facility is located. The objective is to locate facilities to cover all vertices such that the total facility location cost is minimized. In this paper, new upper bounds are proposed for the conditional covering problem on paths, cycles, extended stars, and trees. In particular, we provide an O ( n log n ) -time algorithm for paths, an O ( n 2 log n ) -time algorithm for cycles, an O ( n 1. 5 log n ) -time algorithm for extended stars, and an O ( n 3 ) -time algorithm for trees. Our algorithms for paths, extended stars, and trees improve the previous upper bounds from O ( n 2 ), O ( n 2 ), and O ( n 4 ), respectively.

Details DOI

TCS Journal 2009 Journal Article

Optimal movement of mobile sensors for barrier coverage of a planar region

Binay Bhattacharya
Mike Burmester
Yuzhuang Hu
Evangelos Kranakis
Qiaosheng Shi
Andreas Wiese

Intrusion detection, area coverage and border surveillance are important applications of wireless sensor networks today. They can be (and are being) used to monitor large unprotected areas so as to detect intruders as they cross a border or as they penetrate a protected area. We consider the problem of how to optimally move mobile sensors to the fence (perimeter) of a region delimited by a simple polygon in order to detect intruders from either entering its interior or exiting from it. We discuss several related issues and problems, propose two models, provide algorithms and analyze their optimal mobility behavior.

Details DOI

TCS Journal 2007 Journal Article

Efficient algorithms for center problems in cactus networks

Boaz Ben-Moshe
Binay Bhattacharya
Qiaosheng Shi
Arie Tamir

Efficient algorithms for solving the center problems in weighted cactus networks are presented. In particular, we have proposed the following algorithms for the weighted cactus networks of size n: an O ( n log n ) time algorithm to solve the 1-center problem, and an O ( n log 3 n ) time algorithm to solve the weighted continuous 2-center problem. We have also provided improved solutions to the general p -center problems in cactus networks. The developed ideas are then applied to solve the obnoxious 1-center problem in weighted cactus networks.

Details DOI