Search
Now showing items 1-10 of 19
A distributed algorithm for gathering many fat mobile robots in the plane
(2013)
We revisit the problem of gathering autonomous robots in the plane. In particular, we consider non-transparent unit-disc robots (i.e., fat) in an asynchronous setting with vision as the only means of coordination and robots ...
Complexity of rational and irrational Nash equilibria
(2011)
We introduce two new decision problems, denoted as ∃ RATIONAL NASH and ∃ IRRATIONAL NASH, pertinent to the rationality and irrationality, respectively, of Nash equilibria for (finite) strategic games. These problems ask, ...
The complexity of decision problems about nash equilibria in win-lose games
(2012)
We revisit the complexity of deciding, given a (finite) strategic game, whether Nash equilibria with certain natural properties exist
Universal bufferless routing
(2005)
Given an arbitrary network, and a routing problem with congestion C and dilation D, a long standing open problem is to show the existence of bufferless routing algorithms with optimal performance guarantees (routing time ...
Direct routing: Algorithms and complexity
(2006)
Direct routing is the special case of bufferless routing where N packets, once injected into the network, must be delivered to their destinations without collisions. We give a general treatment of three facets of direct ...
Strength of counting networks
(1996)
This paper shows that any counting network, made up of balancers whose fan-in and fan-out vary arbitrarily, is, indeed, strong enough to simultaneously support both Fetch&Increment and Fetch&Decrement operations, once each ...
Direct routing: Algorithms and complexity
(2004)
Direct routing is the special case of bufferless routing where N packets, once injected into the network, must be routed along specific paths to their destinations without conflicts. We give a general treatment of three ...
An upper and a lower bound for tick synchronization
(1992)
The tick synchronization problem is defined and studied in the semi-synchronous complete network with n processes. An algorithm for the tick synchronization problem enables each process to make an estimate of real time ...
Network game with attacker and protector entities
(2005)
Consider an information network with harmful procedures called attackers (e.g., viruses)
Minimizing expectation plus variance
(2012)
We consider strategic games in which each player seeks a mixed strategy to minimize her cost evaluated by a concave valuation V (mapping probability distributions to reals)