Author name cluster

Robert Benkoczi

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.

4 papers

2 author rows

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 2015 Journal Article

On a class of covering problems with variable capacities in wireless networks

Selim Akl
Robert Benkoczi
Daya Ram Gaur
Hossam Hassanein
Shahadat Hossain
Mark Thom

We consider the problem of allocating clients to base stations in wireless networks. Two design decisions are the location of the base stations, and the power levels of the base stations. We model the interference, due to the increased power usage resulting in greater serving radius, as capacities that are non-increasing with respect to the covering radius. Clients have demands that are not necessarily uniform and the capacity of a facility limits the total demand that can be served by the facility. We consider three models. In the first model, the location of the base stations and the clients are fixed, and the problem is to determine the serving radius for each base station so as to serve a set of clients with maximum total profit subject to the capacity constraints of the base stations. In the second model, each client has an associated demand in addition to its profit. A fixed number of facilities have to be opened from a candidate set of locations. The goal is to serve clients so as to maximize the profit subject to the capacity constraints. In the third model, the location and the serving radius of the base stations are to be determined. There are costs associated with opening the base stations, and the goal is to open a set of base stations of minimum total cost so as to serve the entire demand subject to the capacity constraints at the base stations. We show that for the first model the problem is NP-complete even when there are only two choices for the serving radius, and the capacities are 1, 2. For the second model, we give a 1/2 approximation algorithm. For the third model, we give a column generation procedure for solving the standard linear programming model, and a randomized rounding procedure. We establish the efficacy of the column generation based rounding scheme on randomly generated instances.

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

MFCS Conference 2003 Conference Paper

Faster Algorithms for k -Medians in Trees

Robert Benkoczi
Binay K. Bhattacharya
Marek Chrobak
Lawrence L. Larmore
Wojciech Rytter

Abstract In the k -median problem we are given a connected graph with non-negative weights associated with the nodes and lengths associated with the edges. The task is to compute locations of k facilities in order to minimize the sum of the weighted distances between each node and its closest facility. In this paper we consider the case when the graph is a tree. We show that this problem can be solved in time \(O(n {\mbox{\rm polylog}} (n))\) for the following cases: (i) directed trees (and any fixed k ), (ii) balanced undirected trees, and (iii) undirected trees with k =3.

Details