Author name cluster

Sunil Shende

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.

6 papers

1 author row

TCS Journal 2021 Journal Article

Time-energy tradeoffs for evacuation by two robots in the wireless model

Jurek Czyzowicz
Konstantinos Georgiou
Ryan Killick
Evangelos Kranakis
Danny Krizanc
Manuel Lafond
Lata Narayanan
Jaroslav Opatrny

Two robots stand at the origin of the infinite line and are tasked with searching collaboratively for an exit at an unknown location on the line. They can travel at maximum speed b and can change speed or direction at any time. The two robots can communicate with each other at any distance and at any time. The task is completed when the last robot arrives at the exit and evacuates. We study time-energy tradeoffs for the above evacuation problem. The evacuation time is the time it takes the last robot to reach the exit. The energy it takes for a robot to travel a distance x at speed s is measured as x s 2. The total and makespan evacuation energies are respectively the sum and maximum of the energy consumption of the two robots while executing the evacuation algorithm. Assuming that the maximum speed is b, and the evacuation time is at most cd, where d is the distance of the exit from the origin and c is some positive real number, we study the problem of minimizing the total energy consumption of the robots. We prove that the problem is solvable only for b c ≥ 3. For the case b c = 3, we give an optimal algorithm, and give upper bounds on the energy for the case b c > 3. We also consider the problem of minimizing the evacuation time when the available energy is bounded by Δ. Surprisingly, when Δ is a constant, independent of the distance d of the exit from the origin, we prove that evacuation is possible in time O ( d 3 / 2 log ⁡ d ), and this is optimal up to a logarithmic factor. When Δ is linear in d, we give upper bounds on the evacuation time.

Details DOI

TCS Journal 2020 Journal Article

Priority evacuation from a disk: The case of n = 1,2,3

Jurek Czyzowicz
Konstantinos Georgiou
Ryan Killick
Evangelos Kranakis
Danny Krizanc
Lata Narayanan
Jaroslav Opatrny
Sunil Shende

An exit (or target) is at an unknown location on the perimeter of a unit disk. A group of n + 1 robots (in our case, n = 1, 2, 3 ), initially located at the centre of the disk, are tasked with finding the exit. The robots have unique identities, share the same coordinate system, move at maximum speed 1 and are able to communicate wirelessly the position of the exit once found. Among them there is a distinguished robot called the queen and the remainder of the robots are referred to as servants. It is known that with two robots searching, the room can be evacuated (i. e. , with both robots reaching the exit) in 1 + 2 π 3 + 3 ≈ 4. 8264 time units and this is optimal [11]. Somewhat surprisingly, in this paper we show that if the goal is to have the queen reach the exit, not caring if her servants make it, there is a slightly better strategy for the case of one servant. We prove that this “priority” version of evacuation can be solved in time at most 4. 81854. Furthermore, we show that any strategy for saving the queen with one servant requires time at least 3 + π / 6 + 3 / 2 ≈ 4. 3896 in the worst case. If more servants are available, we show that the time bounds can be improved to 3. 8327 for two servants, and 3. 3738 for three servants which are better than the known lower bound for the corresponding problems of evacuating three or four robots. Finally, we show lower bounds for these cases of 3. 6307 (two servants) and 3. 2017 (three servants). The case of more than three servants uses substantially different techniques and is discussed in a separate paper [13].

Details DOI

TCS Journal 2016 Journal Article

Encoding 2D range maximum queries

Mordecai Golin
John Iacono
Danny Krizanc
Rajeev Raman
Srinivasa Rao Satti
Sunil Shende

We consider the two-dimensional range maximum query (2D-RMQ) problem: given an array containing elements from an ordered set, encode the array so that the position of the maximum element in any specified range of rows and range of columns can be found efficiently. We focus on determining the effective entropy of 2D-RMQ, i. e. , how many bits are needed to encode an array so that 2D-RMQ queries can be answered without accessing the array. We give tight upper and lower bounds on the expected effective entropy for the case when A contains independent identically-distributed random values, and give new upper and lower bounds for the case when the array contains few rows. The latter results improve upon the upper and lower bounds by Brodal et al. [4]. We also give some efficient data structures for 2D-RMQ whose space usage is close to the effective entropy.

Details DOI

TCS Journal 2015 Journal Article

Complexity of barrier coverage with relocatable sensors in the plane

Stefan Dobrev
Stephane Durocher
Mohsen Eftekhari
Konstantinos Georgiou
Evangelos Kranakis
Danny Krizanc
Lata Narayanan
Jaroslav Opatrny

We consider several variations of the problems of covering a set of barriers (modeled as line segments) using sensors that can detect any intruder crossing any of the barriers. Sensors are initially located in the plane and they can relocate to the barriers. We assume that each sensor can detect any intruder in a circular area of fixed range centered at the sensor. Given a set of barriers and a set of sensors located in the plane, we study three problems: (i) the feasibility of barrier coverage, (ii) the problem of minimizing the largest relocation distance of a sensor (MinMax), and (iii) the problem of minimizing the sum of relocation distances of sensors (MinSum). When sensors are permitted to move to arbitrary positions on the barrier, the MinMax problem is shown to be strongly NP-complete for sensors with arbitrary ranges. We also study the case when sensors are restricted to use perpendicular movement to one of the barriers. We show that when the barriers are parallel, both the MinMax and MinSum problems can be solved in polynomial time. In contrast, we show that even the feasibility problem is strongly NP-complete if two perpendicular barriers are to be covered, even if the sensors are located at integer positions, and have only two possible sensing ranges. On the other hand, we give an O ( n 3 / 2 ) algorithm for a natural special case of this last problem.

Details DOI

TCS Journal 2013 Journal Article

A tight characterization of strategic games with a unique equilibrium

Antoniy Ganchev
Lata Narayanan
Sunil Shende

We consider the problem of designing a strategic game (i. e. the utilities) for a set of players where distinct players may have sets of actions with possibly different cardinalities. Furthermore, for each player, a full-support probability distribution on its action set is apriori specified. The goal is to ensure that this pre-specified profile of distributions is the unique Nash equilibrium for the game. One motivation for our problem comes from exponential backoff shared-media access protocols in wireless networks: a static version of protocol compliance can be modeled as an instance of the problem. Building on results from an earlier paper, we provide a tight characterization of the conditions under which such a strategic game may be constructed. Our results not only establish the exact relationship that must hold between the cardinalities of the players’ action sets but also provide the players’ utilities for the desired unique equilibrium to be achieved.

Details DOI

TCS Journal 2008 Journal Article

Games to induce specified equilibria

Antoniy Ganchev
Lata Narayanan
Sunil Shende

Media access protocols in wireless networks require each contending node to wait for a backoff time, chosen randomly from a fixed range, before attempting to transmit on a shared channel. However, nodes acting in their own selfish interest may not follow the protocol. In this paper, a static version of the problem is modeled as a strategic game played by non-cooperating, rational players (the nodes). The objective is to design a game which exhibits a unique, a priori mixed-strategy Nash equilibrium. In the context of the media access problem, the equilibrium of the game would correspond to nodes choosing backoff times randomly from a given range of values, according to the given distribution. We consider natural variations of the problems concerning the number of actions available to the players and show that it is possible to design such a game when there are at least two players that each have the largest number of possible actions among all players. In contrast, we show that if there are exactly two players with different number of actions available to them, then it becomes impossible to design a strategic game with a unique such Nash equilibrium.

Details DOI