Arrow Research search

Author name cluster

Danny Krizanc

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.

21 papers
2 author rows

Possible papers

21

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

Gathering in the plane of location-aware robots in the presence of spies

  • Jurek Czyzowicz
  • Ryan Killick
  • Evangelos Kranakis
  • Danny Krizanc
  • Oscar Morales-Ponce

A set of mobile robots (represented as points) is distributed in the Cartesian plane. The collection contains an unknown subset of byzantine robots which are indistinguishable from the reliable ones. The reliable robots need to gather, i. e. , arrive to a configuration in which at the same time, all of them occupy the same point on the plane. The robots are equipped with GPS devices and at the beginning of the gathering process they communicate the Cartesian coordinates of their respective positions to a central authority. On the basis of this information, and without the knowledge of which robots are faulty, the central authority designs a trajectory for every robot. The central authority aims to provide the trajectories which result in the shortest possible gathering time of the reliable robots. The efficiency of a gathering strategy is measured by its competitive ratio, i. e. , the maximal ratio between the time required for gathering achieved by the given trajectories and the optimal time required for gathering in the offline case, i. e. , when the faulty robots are known to the central authority in advance. The role of the byzantine robots, controlled by the adversary, is to act so that the gathering is delayed and the resulting competitive ratio is maximized. The objective of our paper is to propose efficient algorithms when the central authority is aware of an upper bound on the number of byzantine robots. We give optimal algorithms for collections of robots known to contain at most one faulty robot. When the proportion of byzantine robots is known to be less than one half or one third, we provide algorithms with small constant competitive ratios. We also propose algorithms with bounded competitive ratio in the case where the proportion of faulty robots is arbitrary.

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

Know when to persist: Deriving value from a stream buffer

  • Konstantinos Georgiou
  • George Karakostas
  • Evangelos Kranakis
  • Danny Krizanc

We consider Persistence, a new online problem concerning optimizing weighted observations in a stream of data when the observer has limited buffer capacity. A stream of weighted items arrive one at a time at the entrance of a buffer with two holding locations. A processor (or observer) can process (observe) an item at the buffer location it chooses, deriving this way the weight of the observed item as profit. The main constraint is that the processor can only move synchronously with the item stream. Persistence is the online problem of scheduling the processor movements through the buffer so that its total derived value is maximized under this constraint. We study the performance of the straight-forward heuristic Threshold, i. e. , forcing the processor to “follow” an item through the whole buffer only if its value is above a threshold. We analyze both the optimal offline and Threshold algorithms in the cases where the input stream is either a random permutation, or its items are iid valued. We show that in both cases the competitive ratio achieved by the Threshold algorithm is at least 2/3 when the only statistical knowledge of the items is the median of all possible values. We generalize our results by showing that Threshold, equipped with some minimal statistical advice about the input, achieves competitive ratios in the whole spectrum between 2/3 and 1, following the variation of a newly defined density-like measure of the input. This result is a significant improvement over the case of arbitrary input streams, where we show that no online algorithm can achieve a competitive ratio better than 1/2.

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

Excuse me! or the courteous theatregoers' problem

  • Konstantinos Georgiou
  • Evangelos Kranakis
  • Danny Krizanc

Consider a theatre consisting of m rows each containing n seats. Theatregoers enter the theatre along aisles and pick a row which they enter along one of its two entrances so as to occupy a seat. Assume they select their seats uniformly and independently at random among the empty ones. A row of seats is narrow and an occupant who is already occupying a seat is blocking passage to new incoming theatregoers. As a consequence, occupying a specific seat depends on the courtesy of theatregoers and their willingness to get up so as to create free space that will allow passage to others. Thus, courtesy facilitates and may well increase the overall seat occupancy of the theatre. We say a theatregoer is courteous if (s)he will get up to let others pass. Otherwise, the theatregoer is selfish. A set of theatregoers is courteous with probability p (or p-courteous, for short) if each theatregoer in the set is courteous with probability p, randomly and independently. It is assumed that the behaviour of a theatregoer does not change during the occupancy of the row. Thus, p = 1 represents the case where all theatregoers are courteous and p = 0 when they are all selfish. In this paper, we are interested in the following question: what is the expected number of occupied seats as a function of the total number of seats in a theatre, n, and the probability that a theatregoer is courteous, p? We study and analyze interesting variants of this problem reflecting behaviour of the theatregoers as entirely selfish, and p-courteous for a row of seats with one or two entrances and as a consequence for a theatre with m rows of seats with multiple aisles. We also consider the case where seats in a row are chosen according to the geometric distribution and the Zipf distribution (as opposed to the uniform distribution) and provide bounds on the occupancy of a row (and thus the theatre) in each case. Finally, we propose several open problems for other seating probability distributions and theatre seating arrangements.

Details DOI

TCS Journal 2008 Journal Article

Memoryless search algorithms in a network with faulty advice

  • Nicolas Hanusse
  • Dimitris Kavvadias
  • Evangelos Kranakis
  • Danny Krizanc

In this paper, we present a randomized algorithm for a mobile agent to search for an item stored at a node t of a network, without prior knowledge of its exact location. Each node of the network has a database that will answer queries of the form “how do I find t? ” by responding with the first edge on a shortest path to t. It may happen that some nodes, called liars, give bad advice. We investigate a simple memoryless algorithm which follows the advice with some fixed probability q > 1 / 2 and otherwise chooses a random edge. If the degree of each node and number of liars k are bounded, we show that the expected number of edges traversed by the agent before finding t is bounded from above by O ( d + r k ), where d is the distance between the initial and target nodes and r = q 1 − q. We also show that this expected number of steps can be significantly improved for particular topologies such as the complete graph and the torus.

Details DOI

TCS Journal 2006 Journal Article

Asynchronous deterministic rendezvous in graphs

  • Gianluca De Marco
  • Luisa Gargano
  • Evangelos Kranakis
  • Danny Krizanc
  • Andrzej Pelc
  • Ugo Vaccaro

Two mobile agents (robots) having distinct labels and located in nodes of an unknown anonymous connected graph have to meet. We consider the asynchronous version of this well-studied rendezvous problem and we seek fast deterministic algorithms for it. Since in the asynchronous setting, meeting at a node, which is normally required in rendezvous, is in general impossible, we relax the demand by allowing meeting of the agents inside an edge as well. The measure of performance of a rendezvous algorithm is its cost: for a given initial location of agents in a graph, this is the number of edge traversals of both agents until rendezvous is achieved. If agents are initially situated at a distance D in an infinite line, we show a rendezvous algorithm with cost O ( D | L min | 2 ) when D is known and O ( ( D + | L max | ) 3 ) if D is unknown, where | L min | and | L max | are the lengths of the shorter and longer label of the agents, respectively. These results still hold for the case of the ring of unknown size, but then we also give an optimal algorithm of cost O ( n | L min | ), if the size n of the ring is known, and of cost O ( n | L max | ), if it is unknown. For arbitrary graphs, we show that rendezvous is feasible if an upper bound on the size of the graph is known and we give an optimal algorithm of cost O ( D | L min | ) if the topology of the graph and the initial positions are known to agents.

Details DOI

MFCS Conference 2005 Conference Paper

Asynchronous Deterministic Rendezvous in Graphs

  • Gianluca De Marco
  • Luisa Gargano
  • Evangelos Kranakis
  • Danny Krizanc
  • Andrzej Pelc
  • Ugo Vaccaro

Abstract Two mobile agents (robots) having distinct labels and located in nodes of an unknown anonymous connected graph, have to meet. We consider the asynchronous version of this well-studied rendezvous problem and we seek fast deterministic algorithms for it. Since in the asynchronous setting meeting at a node, which is normally required in rendezvous, is in general impossible, we relax the demand by allowing meeting of the agents inside an edge as well. The measure of performance of a rendezvous algorithm is its cost: for a given initial location of agents in a graph, this is the number of edge traversals of both agents until rendezvous is achieved. If agents are initially situated at a distance D in an infinite line, we show a rendezvous algorithm with cost O ( D | L min | 2 ) when D is known and O (( D + | L max |) 3 ) if D is unknown, where | L min | and | L max | are the lengths of the shorter and longer label of the agents, respectively. These results still hold for the case of the ring of unknown size but then we also give an optimal algorithm of cost O ( n | L min |), if the size n of the ring is known, and of cost O ( n | L max |), if it is unknown. For arbitrary graphs, we show that rendezvous is feasible if an upper bound on the size of the graph is known and we give an optimal algorithm of cost O ( D | L min |) if the topology of the graph and the initial positions are known to agents.

Details

MFCS Conference 1996 Conference Paper

Minimizing Congestion of Layouts for ATM Networks with Faulty Links

  • Leszek Gasieniec
  • Evangelos Kranakis
  • Danny Krizanc
  • Andrzej Pelc

Abstract We consider the problem of constructing virtual path layouts for an ATM network consisting of a complete network K n of n processors in which a certain number of links may fail. Our main goal is to construct layouts which tolerate any configuration of up to f layouts and have a least possible congestion. First, we study the minimal congestion of 1-hop f -tolerant layouts in K n. For any positive integer f we give upper and lower bounds on this minimal congestion and construct f -tolerant layouts with congestion corresponding to the upper bounds. Our results are based on a precise analysis of the diameter of the network K n [ \(\mathcal{F}\) ] which results from K n by deleting links from a set \(\mathcal{F}\) of bounded size. Next we study the minimal congestion of h -hop f -tolerant layouts in K n, for larger values of the number h of hops. We give upper and lower bounds on the order of magnitude of this congestion, based on results for 1-hop layouts. Finally, we consider a random, rather than worst case, fault distribution. Links fail independently with constant probability p}<1. Our goal now is to construct layouts with low congestion that tolerate the existing faults with high probability. For any p}<1, we show such layouts in K n, with congestion O (log n ).

Details

MFCS Conference 1995 Conference Paper

String Recognition on Anonymous Rings

  • Evangelos Kranakis
  • Danny Krizanc
  • Flaminia L. Luccio

Abstract We consider the problem of recognizing whether a given binary string of length n is equal (up to rotation) to the input of an anonymous oriented ring of n processors. Previous algorithms for this problem have been “global” and do not take into account “local” patterns occurring in the string. Such patterns may be repetitive or discriminating, and can be used to provide efficient algorithms for recognizing strings. In this paper we give new upper and lower bounds on the bit complexity of string recognition. For the case of periodic strings, near optimal bounds are given which depend on the period of the string. For the case of a randomly chosen string, an optimal algorithm for the problem is given. In particular, we show that almost all strings can be recognized by communicating θ(n log n) bits. It is interesting to note that Kolmogorov complexity theory is used in the proof of our upper bound, rather than its traditional application to the proof of lower bounds.

Details

FOCS Conference 1993 Conference Paper

Universal Emulations with Sublogarithmic Slowdown

  • Christos Kaklamanis
  • Danny Krizanc
  • Satish Rao

The existence of bounded degree networks which can emulate the computation of any bounded degree network of the same size with logarithmic slowdown is well-known. The butterfly is an example of such a universal network. Leiserson was the first to introduce the concept of an area-universal network: a network with VLSI layout area A which can emulate any network of the same size and layout area with logarithmic slowdown. His results imply the existence of an N-node network with layout area O(N log/sup 2/ N) which can emulate any N-node planar network with O(log N) slowdown. The main results of this paper are: There exists an N-node network with layout area O(N log/sup 2/ N) which can emulate any N-node planar network with O(loglogN) slowdown. The N-node butterfly (and hypercube) can emulate any network with VLSI layout area N/sup 2-/spl epsiv// (/spl epsiv/>0) with O(loglogN) slowdown. We also discuss sublogarithmic bounds for the slowdown of emulations of arbitrary bounded degree networks. >

Details

FOCS Conference 1987 Conference Paper

The Complexity of Parallel Comparison Merging

  • Mihály Geréb-Graus
  • Danny Krizanc

We prove a worst case lower bound of Ω(log log n) for randomized algorithms merging two sorted lists of length n in parallel using n processors on Valiant's parallel computation tree model. We show how to strengthen this result to a lower bound for the expected time taken by any algorithm on the uniform distribution. Finally, bounds are given for the average time required for the problem when the number of processors is less than and greater than n.

Details