Online Dynamic Programming Speedups ∗ (2009)
Amotz Bar-noy, Mordecai J. Golin, Yan Zhang
Consider the dynamic program h(n) = min1≤j≤n a(n, j), where a(n, j) is some formula that may (online) or may not (offline) depend on the previously computed h(i), for i < n. The goal is to...
An Ontology-Centric Approach to Sensor-Mission Assignment (2009)
Mario Gomez, Alun Preece, Matthew P. Johnson, Geeth De Mel, Christopher Gibson, Amotz Bar-noy, ...
Abstract. Sensor-mission assignment involves the allocation of sensor and other information-providing resources to missions in order to cover the information needs of the individual tasks in each...
Abstract On the Complexity of Radio Communication (Extended Abstract) (2008)
Noga Alon, Amotz Bar-noy, Nathan Linial, David Peleg
A radio network is a synchronous network of processors that communicate by transmitting messages to their neighbors. A processor receives a message in a given step if and only if it is silent then...
ABSTRACT Conflict-Free Coloring for Intervals: from Offline to Online (2008)
This paper studies deterministic algorithms for a frequency assignment problem in cellular networks. A cellular network consists of fixed-position base stations and moving agents. Each base station...
Amotz Bar-noy, Boaz Patt-shamir, Igor Ziper
Abstract. In broadcast disks systems, information is broadcasted in a shared medium. When a client needs an item from the disk, it waits until that item is broadcasted. Broadcast disks systems are...
Competitive On-Line Paging Strategies for Mobile Users Under Delay Constraints ABSTRACT (2008)
A mobile user is roaming in a zone of n cells in a cellular network system. When a call for the mobile arrives, the system pages the mobile in these cells since it never reports its location unless...
Online Dynamic Programming Speedups ⋆ (2008)
Amotz Bar-noy, Mordecai J. Golin, Yan Zhang
Abstract. Consider the Dynamic Program h(n) = min1≤j≤n a(n, j) for n =1, 2,...,N. For arbitrary values of a(n, j), calculating all the h(n) requires Θ(N 2) time. It is well known that, if the...
Windows Scheduling of Arbitrary Length Jobs on Parallel Machines (2008)
Amotz Bar-noy, Richard E. Ladner, Tami Tamir, Tammy Vandegrift
Amotz Bar-noy, Panagiotis Cheilaris, Svetlana Olonetsky, Shakhar Smorodinsky
conflict-free coloring for geometric hypergraphs
Amotz Bar-noy, Joseph Naor, Moni Naor
Many algorithms in distributed systems assume that the size of a single message depends on the number of processors. In this paper, we assume in contrast that messages consist of a single bit. Our...
A Tiling Approach for Fast Implementation of the Traveling Tournament Problem (2008)
Introduction Sports in society today are played by millions of individuals at the professional, scholastic and amateur levels. The success of the leagues and tournaments often lies in the ability to...
Amotz Bar-noy, Sudipto Guha, Joseph (se Naor, Baruch Schieber
We consider the following fundamental scheduling problem. The input to the problem consists of n jobs and k machines. Each of the jobs is associated with a release time, a deadline, a weight, and a...
Approximating the Throughput of Multiple Machines in Real-Time Scheduling (2007)
Amotz Bar-noy, Sudipto Guha, Joseph (Seffi) Naor, Baruch Schieber
We consider the following fundamental scheduling problem. The input to the problem consists of n jobs and k machines. Each of the jobs is associated with a release time, a deadline, a weight, and a...
A Lower Bound for On-Line Edge Coloring (2007)
Amotz Bar-noy, Rajeev Motwani, Joseph Naor
Introduction Let G = (V; E) be a simple graph. The chromatic number of a graph, Ø(G), is the minimum number of colors needed to color the vertices such that adjacent vertices receive different...
Amotz Bar-noy, Frank K. Hwang, Ilan Kessler, Shay Kutten
Algorithms for the group testing problem when there is no a priori information on the number of defective items are considered. The efficiency criterion used is the competitive ratio, which is the...
Alok Aggarwal, Amotz Bar-noy, Rajiv Ramaswami, Baruch Schieber, Madhu Sudan
This paper studies the problem of dedicating routes to connections in optical networks. In optical networks, the vast bandwidth available in an optical ber is utilized by partitioning it into several...
Amotz Bar-noy, Sudipto Guha, Yoav Katz, Joseph (seffi Naor, Baruch Schieber, Hadas Shachnai
z--We consider the following scheduling with batching problem that has many applications, e.g., in multimedia-on-demand and manufacturing of integrated circuits. The input to the problem consists of...
Amotz Bar-noy, Alain Mayer, Baruch Schieber
We introduce a new scheduling problem that is motivated by applications in the area of access and ow-control in high-speed and wireless networks. An instance of the problem consists of a set of...
Amotz Bar-noy, Alain Mayer, Baruch Schieber
We introduce a new scheduling problem that is motivated by applications in the area of access and ow-control of high-speed and wireless networks. An instance of the problem consists of a set of...
Alok Aggarwal, Amotz Bar-noy, Samir Khuller, Dina Kravets, Baruch Schieber
We present efficient algorithms for finding a minimum cost perfect matching, and for solving the transportation problem in bipartite graphs, G = (Sinks [ Sources; Sinks 2 Sources), where jSinksj = n,...
Magn'us M. Halld'orsson (2007)
Amotz Bar-noy, Guy Kortsarz, Ravit Salman, Hadas Shachnai
bar-noy et al., sum multicoloring of graphs. Address for Proofs: Dr. Hadas Shachnai
Magn'us M. Halld'orsson (2007)
In the minimum sum coloring problem, the goal is to color the vertices of a graph with the positive integers such that the sum of all colors is minimal. Iteratively coloring maximum independent sets...
Amotz Bar-noy, Ari Freund, Joseph (seffi Naor
Abstract. In a hierarchical server environment, jobs must be assigned in an on-line fashion to a collection of servers forming a hierarchy of capability. Each job requests a specific server meeting...
Off-line and On-line Guaranteed Start-Up Delay for Media-on-Demand with Stream Merging (2007)
Amotz Bar-noy, Justin Goshi, Richard E. Ladner
We address the problem of designing ecient algorithms for media-on-demand in systems that use stream merging. In the stream merging model the receiving bandwidth of clients is larger than the...
A survey of sensor selection schemes in wireless sensor networks (2007)
Hosam Rowaihy, Sharanya Eswaran, Matthew Johnson, Dinesh Verma, Amotz Bar-noy, Theodore Brown
One of the main goals of sensor networks is to provide accurate information about a sensing field for an extended period of time. This requires collecting measurements from as many sensors as...
A mobile user roams in a zone of N cells. The system knows an a priori probability for the mobile being in each one of the cells. Delay constraint: The mobile must be found in D paging rounds, each...
Paging mobile users efficiently and optimally (2007)
Abstract — A mobile user is roaming in a zone composed of N cells in a cellular network system. When a call to the mobile user arrives, the system pages the mobile user in these cells since it...
A survey of sensor selection schemes in wireless sensor networks (2007)
Hosam Rowaihy, Sharanya Eswaran, Matthew Johnson, Dinesh Verma, Amotz Bar-noy, Theodore Brown, ...
Abstract — One of the main goals of many sensor networks is to provide accurate information about a sensing field for an extended period of time. This requires collecting measurement from as many...
Optimal Delay for Media-on-Demand with Pre-loading and Pre-buffering (2006)
Amotz Bar-noy, Richard E. Ladner, Tami Tamir
Broadcasting popular media to clients is the ultimate scalable solution for media-ondemand. The simple solution of downloading and viewing the media from one channel cannot guarantee a reasonable...
Online conflict-free colorings for hypergraphs, manuscript (2006)
Amotz Bar-noy, Panagiotis Cheilaris, Svetalana Olonetsky, Shakhar Smorodinsky
(i) We provide a framework for online conflict-free coloring (CF-coloring) any hypergraph. We use this framework to obtain an efficient randomized online algorithm for CF-coloring any k-degenerate...
Online conflict-free colorings for hypergraphs, manuscript (2006)
Amotz Bar-noy, Panagiotis Cheilaris, Svetalana Olonetsky, Shakhar Smorodinsky
We provide a framework for online conflict-free coloring (CF-coloring) of any hypergraph. We use this framework to obtain an efficient randomized online algorithm for CF-coloring any k-degenerate...
Sharing Memory Robustly in Message-Passing Systems (2005)
Attiya, Hagit, Bar-Noy, Amotz, Dolev, Danny
Emulators that translate algorithms from the shared-memory model to two different message-passing models are presented. Both are achieved by implementing a wait-free, atomic, single-writer...
Establishing a mobile conference call under delay and bandwidth constraints (2004)
Abstract — The issue of tracking a group of users is discussed in this study. Given the condition that the search is over only after all the users in the group are found, this problem is called the...
Windows Scheduling as a Restricted Version of Bin Packing (2004)
Amotz Bar-noy, Richard E. Ladner, Tami Tamir
Given is a sequence of n positive integers w1, w2,..., wn that are associated with the items 1, 2,..., n respectively. In the windows scheduling problem, the goal is to schedule all the items (equal...
Establishing Wireless Conference Calls Under Delay Constraints (2004)
Amotz Bar-noy, Grzegorz Malewicz
A prevailing feature of mobile telephony systems is that the cell where a mobile user is located may be unknown. Therefore when the system is to establish a call between users it may need to search,...
Scheduling Techniques for Media-on-Demand (2003)
Amotz Bar-noy, Richard E. Ladner, Tami Tamir
Broadcasting popular media to clients is the ultimate scalable solution for media-ondemand. Recently, it was shown that if clients can receive data at a rate faster than what they need for playback...
Comparison of Stream Merging Algorithms for Media-on-Demand (2003)
Amotz Bar-noy, Justin Goshi, Richard E. Ladner, Kenneth Tam
Stream merging is a technique for eciently delivering popular media-on-demand using multicast and client buers. Recently, several algorithms for stream merging have been proposed, and we perform a...
Establishing Wireless Conference Calls under Delay Constraints (2003)
Amotz Bar-noy, Grzegorz Malewicz
A prevailing feature of mobile telephony systems is that the cell where a mobile user is located may be unknown. Therefore, when the system is to establish a call between users, it may need to...
Pushing dependent data in clients-providers-servers systems (2003)
Amotz Bar-noy, Baruch Schieber
In satellite and wireless networks and in advanced traffic information systems in which the up-link bandwidth is very limited, a server broadcasts data files in a round-robin manner. The data files...
Processor Renaming in Asynchronous Environments. (2002)
Fischer, Lynch and Paterson FLP proved that in a completely asynchronous system weak agreement cannot be achieved even in the presence of a single benign fault. Following the direction proposed in...
Noga Alon, Nathan Linial, Amotz Bar-noy, David Peleg
A radio network is a synchronous network of processors that communicate by trans-mitting messages to their neighbors. A processor receives a message in a given step if and only if it is silent then...
Efficient Periodic Scheduling by Trees (2002)
Amotz Bar-noy, Vladimir Dreizin, Boaz Patt-shamir
Abstract — In a perfectly-periodic schedule, time is divided into time-slots, and each client gets a time slot precisely every predefined number of time slots. The input to a schedule design...
Efficient Periodic Scheduling by Trees (2002)
Amotz Bar-noy, Vladimir Dreizin, Boaz Patt-shamir
Abstract—Ina perfectly-periodic schedule, time is divided into time-slots, and each client gets a time slot precisely every predefined number of time slots. The input to a schedule design algorithm...
Competitive on-line switching policies (2002)
Amotz Bar-noy, Ari Freund, Shimon Landa, Joseph (seffi Naor
A switch, or server, serves n input queues, processing messages arriving at these queues to a single output channel. At each time slot the switch can process a single message from one of the queues....
Efficient Periodic Scheduling by Trees (2002)
Amotz Bar-noy, Vladimir Dreizin, Boaz Patt-shamir
Abstract—Ina perfectly-periodic schedule, time is divided into time-slots, and each client gets a time slot precisely every predefined number of time slots. The input to a schedule design algorithm...
Competitive On-Line Stream Merging Algorithms for Media-on-Demand (2002)
Amotz Bar-noy, Richard E. Ladner
We consider the problem of minimizing the bandwidth needed by media-on-demand servers that use stream merging. We consider the on-line case where client requests are not known ahead of time. To...
Nearly Optimal Perfectly-Periodic Schedules (2001)
Amotz Bar-noy, Aviv Nisgav, Boaz Patt-shamir
We study the problem of scheduling infinitely ¢ often jobs, each with an associated demand probability, under the constraint that each job must be scheduled with a fixed period. That is, the number...
A unified approach to approximating resource allocation and scheduling (2001)
Amotz Bar-Noy, Reuven Bar-Yehuda, Ari Freund, Joseph (Seffi) Naor, Baruch Schieber
A unified approach to approximating resource allocation and scheduling (2001)
Amotz Bar-Noy, Reuven Bar-Yehuda, Ari Freund, Joseph (Seffi) Naor, Baruch Schieber
We present a general framework for solving resource allocation and scheduling problems. Given a resource of fixed size, we present algorithms that approximate the maximum throughput or the minimum...
Nearly Optimal Perfectly-Periodic Schedules (2001)
Amotz Bar-noy, Aviv Nisgav, Boaz Patt-shamir
We study the problem of scheduling innitely often M jobs, each with an associated demand probability w i, under the constraint that each job must be scheduled with a xed period. That is, the number...
Efficient algorithms for optimal stream merging for media-on-demand (2001)
Amotz Bar-Noy, Richard E. Ladner
We address the problem of designing optimal off-line algorithms that minimize the required bandwidth for media-on-demand systems that use stream merging. We concentrate on the case where clients can...
Establishing Wireless Conference Calls under Delay Constraints (2001)
Amotz Bar-noy, Grzegorz Malewicz
A prevailing feature of mobile telephony systems is that the cell where a mobile user is located may be unknown. Therefore when the system is to establish a call between users it may need to search,...
Efficient algorithms for optimal stream merging for media-on-demand (2001)
Amotz Bar-Noy, Richard E. Ladner
We address the problem of designing optimal off-line algorithms that minimize the required bandwidth for media-on-demand systems that use stream merging. We concentrate on the case where clients can...
A unified approach to approximating resource allocation and scheduling (2000)
Amotz Bar-Noy, Reuven Bar-Yehuda, Ari Freund, Joseph (Seffi) Naor, Baruch Schieber
We present a general framework for solving resource allocation and scheduling problems. Given a resource of fixed size, we present algorithms that approximate the maximum throughput or the minimum...
New Algorithms for Related Machines with Temporary Jobs (2000)
Amotz Bar-noy, Ari Freund, Joseph (seffi Naor
We consider the on-line problem of assigning temporary jobs to related machines. In this model machines have speeds and the jobs are weighted and may be temporary (i.e. may expire after some unknown...
Competitive On-Line Stream Merging Algorithms for Media-on-Demand (2000)
Amotz Bar-noy, Richard E. Ladner
We consider the problem of minimizing the bandwidth needed by media-on-demand servers that use stream merging. We consider the on-line case where client requests are not known ahead of time. To...
Broadcast Disks with Polynomial Cost Functions (2000)
Amotz Bar-noy, Boaz Patt-Shamir, Igor Ziper
In broadcast disk systems, information is broadcasted in a shared medium. When a client needs an item from the disk, it waits until that item is broadcasted. The fundamental algorithmic problem for...
Efficient algorithms for optimal stream merging for media-on-demand (2000)
Amotz Bar-noy, Richard E. Ladner
We address the problem of designing optimal off-line algorithms that minimize the required bandwidth for media-on-demand systems that use stream merging. We concentrate on the case where clients can...
Sum Multi-Coloring of Graphs (Extended Abstract) (1999)
Amotz Bar-noy, Guy Kortsarz, Ravit Salman, Hadas Shachnai
) Amotz Bar-Noy Magn'us M. Halld'orsson y Guy Kortsarz z Ravit Salman x Hadas Shachnai -- Abstract Scheduling dependent jobs on multiple machines is modeled by the graph multi-coloring...
Broadcasting Multiple Messages in the Multiport Model (1999)
We consider the problem of broadcasting multiple messages from one processor to many processors in the k-port model for message passing systems. In such systems, processors communicate in rounds,...
The minimum color-sum of bipartite graphs (1998)
The problem of minimum color sum of a graph is to color the vertices of the graph such that the sum (average) of all assigned colors is minimum. Recently, in [BBH
Message Multicasting In Heterogeneous Networks (1998)
Amotz Bar-Noy, Sudipto Guha, Joseph (Seffi) Naor, Baruch Schieber
In heterogeneous networks, sending messages may incur different delays on different links, and each node may have a different switching time between messages. The well studied Telephone model is...
On Chromatic Sums and Distributed Resource Allocation (1998)
Amotz Bar-noy, Mihir Bellare, Hadas Shachnai, Tami Tamir
This paper studies an optimization problem that arises in the context of distributed resource allocation: Given a conflict graph that represents the competition of processors over resources, we seek...
Multicasting in Heterogeneous Networks (1998)
Amotz Bar-noy, Sudipto Guha, Joseph (Seffi) Naor, Baruch Schieber
In heterogeneous networks sending messages may incur different delays on different links, and each node may have a different switching time between messages. The well studied Telephone model is...
Competitive Dynamic Bandwidth Allocation (1998)
Amotz Bar-noy, Yishay Mansour, Baruch Schieber
We propose a realistic theoretical model for dynamic bandwidth allocation. Our model takes into account the two classical quality of service parameters: latency and utilization, together with a newly...
Competitive Dynamic Bandwidth Allocation (1998)
Amotz Bar-noy, Yishay Mansour, Baruch Schieber
We propose a realistic theoretical model for dynamic bandwidth allocation. Our model takes into account the two classical quality of service parameters: latency and utilization, together with a newly...
Optimal Broadcasting of Two Files over an Asymmetric Channel (1998)
We study the problem of scheduling files over a broadcast channel in an asymmetric environment. The goal is to minimize the mean response time for clients who access the broadcast channel. Asymmetric...
On Chromatic Sums and Distributed Resource Allocation (1998)
Amotz Bar-noy, Mihir Bellare, Magnús M. Halldórsson, Hadas Shachnai, Tami Tamir
This paper studies an optimization problem that arises in the context of distributed resource allocation: Given a conflict graph that represents the competition of processors over resources, we seek...
Minimizing Service and Operation Costs of Periodic Scheduling (1998)
Amotz Bar-noy, Randeep Bhatia, Joseph (Seffi) Naor, Baruch Schieber
We study the problem of scheduling activities of several types under the constraint that at most a fixed number of activities can be scheduled in any single time-slot. Any given activity type is...
Minimizing Service and Operation Costs of Periodic Scheduling (1998)
Amotz Bar-noy, Randeep Bhatia, Joseph (seffi Naor, Baruch Schieber
We study the problem of scheduling activities of several types under the constraint that at most a fixed number of activities can be scheduled in any single time-slot. Any given activity type is...
Sorting, Minimal Feedback Sets and Hamilton Paths in Tournaments, (1997)
We present a general method for translating sorting by comparisons to algorithms that compute a Hamilton path in a tournament. The translation is based on the relation between minimal feedback sets...
Square Meshes are not Always Optimal, (1997)
In this paper we consider mesh connected computers with multiple buses, providing broadcast facilities along rows and columns. A tight bound of theta(n(1/2)) is established for the number of rounds...
Round Robin Policies for Packet Switching (1997)
In a packet switching system a switch serves n buffers by delivering packets that arrive at these buffers. The switch can serve only integral packets one at a time. The goal is to minimize the size...
Bandwidth Allocation with Preemption (1997)
Amotz Bar-noy, Ran Canetti, Shay Kutten, Yishay Mansour, Baruch Schieber
Bandwidth allocation is a fundamental problem in the design of networks where bandwidth has to be reserved for connections in advance. The problem is intensified when the overall requested bandwidth...
Minimum Color Sum of Bipartite Graphs (1997)
The problem of minimum color sum of a graph is to color the vertices of the graph such that the sum (average) of all assigned colors is minimum. Recently, in [BBH + 96], it was shown that in general...
Efficient routing in optical networks (1996)
Alok Aggarwal, Amotz Bar-noy, Rajiv Ramaswami, Baruch Schieber, Madhu Sudan
This paper studies the problems of dedicating routes to connections in optical networks. In optical networks, the vast bandwidth available in an optical fiber is utilized by partitioning it into...
Efficient Routing in Optical Networks (1996)
Alok Aggarwal, Amotz Bar-noy, Don Coppersmith, Rajiv Ramaswami, Baruch Schieber, Madhu Sudan
This paper studies the problem of dedicating routes to connections in optical networks. In optical networks, the vast bandwidth available in an optical fiber is utilized by partitioning it into...
Topology-Based Tracking Strategies for Personal Communication Networks (1996)
Amotz Bar-noy, Ilan Kessler, Mahmoud Haghshineh, Mahmoud Naghshineh
This paper explores tracking strategies for mobile users in personal communication networks which are based on the topology of the cells. We introduce the notion of
Optimal Multiple Message Broadcasting in Telephone-Like Communication Systems (1996)
Amotz Bar-noy, Shlomo Kipnis, Baruch Schieber
We consider the problem of broadcasting multiple messages from one processor to many processors in telephone-like communication systems. In such systems, processors communicate in rounds, where in...
Guaranteeing Fair Service to Persistent Dependent Tasks (1996)
Amotz Bar-noy, Alain Mayer, Baruch Schieber, Madhu Sudan
We introduce a new scheduling problem that is motivated by applications in the area of access and flow-control in high-speed and wireless networks. An instance of the problem consists of a set of...
Mobile Users: To Update or not to Update? (1996)
Amotz Bar-noy, Ilan Kessler, Moshe Sidi
Tracking strategies for mobile users in wireless networks are studied. In order to save the cost of using the wireless links mobile users should not update their location whenever they cross...
The Complexity of Finding Most Vital Arcs and Nodes (1995)
Bar-Noy, Amotz, Khuller, Samir, Schieber, Baruch
Let $G(V,E)$ be a graph (either directed or undirected) with a non-negative length $\ell(e)$ associated with each arc $e$ in $E$. For two specified nodes $s$ and $t$ in $V$, the $k$ most vital arcs...
The Complexity of Finding Most Vital Arcs and Nodes (1995)
Bar-Noy, Amotz, Khuller, Samir, Schieber, Baruch
Let $G(V,E)$ be a graph (either directed or undirected) with a non-negative length $\ell(e)$ associated with each arc $e$ in $E$. For two specified nodes $s$ and $t$ in $V$, the $k$ most vital arcs...
Computing global combine operations in the multiport postal model (1995)
Bar-Noy, Amotz, Bruck, Jehoshua, Ho, Ching-Tien, Kipnis, Shlomo, Schieber, Baruch
Consider a message-passing system of n processors, in which each processor holds one piece of data initially. The goal is to compute an associative and commutative reduction function on the n pieces...
The complexity of finding most vital arcs and nodes (1995)
Amotz Bar-noy, Samir Khuller, Baruch Schieber
Let G(V; E) be a graph (either directed or undirected) with a non-negative length `(e) associated with each arc e in E. For two specified nodes s and t in V, the k most vital arcs (or nodes) are...
Bandwidth Allocation with Preemption (1995)
Amotz Bar-noy, Ran Canetti, Shay Kutten, Yishay Mansour, Baruch Schieber
Bandwidth allocation is a fundamental problem in the design of networks that allocate, in advance, bandwidth to connections. The problem is intensified when and acceptance/rejection decisions on...
Guaranteeing Fair Service to Persistent Dependent Tasks (1995)
Amotz Bar-noy, Alain Mayer, Baruch Schieber
We introduce a new scheduling problem that is motivated by applications in the area of access and flow-control in high-speed and wireless networks. An instance of the problem consists of a set of...
Bandwidth Allocation with Preemption (1995)
Amotz Bar-noy, Ran Canetti, Shay Kutten, Yishay Mansour, Baruch Schieber
Bandwidth allocation is a fundamental problem in the design of networks where bandwidth has to be reserved for connections in advance. The problem is intensified when the requested bandwidth exceeds...
Bandwidth allocation with preemption (1995)
Amotz Bar-noy, Ran Canetti, Shay Kutten, Yishay Mansour, Baruch Schieber
Bandwidth allocation is a fundamental problem in the design of networks where bandwidth has to be reserved for connections in advance. The problem is intensi ed when the overall requested bandwidth...
Efficient routing and scheduling algorithms for optical networks (1994)
Alok Aggarwal, Amotz Bar-noy, Rajiv Ramaswami, Baruch Schieber, Madhu Sudan
This paper studies the problems of dedicating routes and scheduling transmissions in optical networks. In optical networks, the vast bandwidth available in an optical fiber is utilized by...
Mobile Users: To Update or not to Update? (1994)
This paper focuses on three natural strategies in which the mobile users make the decisions when and where to update: the time-based strategy, the number of movements-based strategy, and the...
Compact Distributed Data Structures for Adaptive Routing (1994)
Baruch Awerbuch, Amotz Bar-noy, Nathan Linial, David Peleg
In designing a routing scheme for a communication network it is desirable to use as short as possible paths for routing messages, while keeping the routing information stored in the processors'...
Efficient Minimum Cost Matching and Transportation Using Quadrangle Inequality (1993)
Aggarwal, Alok, Bar-Noy, Amotz, Khuller, Samir, Kravets, Dina, Schieber, Baruch
We present efficient algorithms for finding a minimum cost perfect matching, and for solving the transportation problem in bipartite graphs, G=(\Red\cup \Blue, \Red\times \Blue), where |\Red|=n,...
Efficient Minimum Cost Matching and Transportation Using Quadrangle Inequality (1993)
Aggarwal, Alok, Bar-Noy, Amotz, Khuller, Samir, Kravets, Dina, Schieber, Baruch
We present efficient algorithms for finding a minimum cost perfect matching, and for solving the transportation problem in bipartite graphs, G=(\Red\cup \Blue, \Red\times \Blue), where |\Red|=n,...
Tracking Mobile Users in Wireless Communications Networks (1993)
Tracking strategies for mobile wireless networks are studied. We assume a cellular architecture where base stations that are interconnected by a wired network communicate with mobile units via...
Designing Broadcasting Algorithms in the Postal Model for Message-Passing Systems (1992)
Amotz Bar-noy, Shlomo Kipnis, Shlomo Kipnis
In many distributed-memory parallel computers and high-speed communication networks, the exact structure of the underlying communication network may be ignored. These systems assume that the network...
Compact Distributed Data Structures for Adaptive Routing (1989)
Baruch Awerbuch, Amotz Bar-noy, Nathan Linial, David Peleg
In designing a routing scheme for a communication network it is desirable to use as short as possible paths for routing messages, while keeping the routing information stored in the processors'...
Distributed Computing (1991) 4:105-110 Consensus algorithms with one-bit messages* (1987)
in 1987, both from the Hebrew
Shifting Gears: Changing Algorithms on the Fly to Expedite Byzantine Agreement (1987)
Amotz Bar-noy, Danny Dolev, Cynthia Dwork, H Raymond Strong
We describe several new algorithms for Byzantine agreement. The first of-these is a simplification of the original exponential-time Byzantine agreement algorithm due to Pease, Shostak, and Lamport,...