Author name cluster

Alon Itai

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.

8 papers

2 author rows

TCS Journal 2002 Journal Article

The passport control problem or how to keep a dynamic service system load balanced?

Alon Itai
Michael Rodeh
Hadas Shachnai

In many real life situations (such as department stores, or passport control booths in airports) parallel queues are formed in front of control stations. Typically, some of the stations are manned while others are not. Classical queuing theory considers the configuration constant, and concentrates on the arrival process. This work explores a new line of research—the case in which the configuration is dynamic, and the customers can plan to cope with anticipated changes. Specifically, as the queues build up, management assigns additional officers to the unmanned stations. When this happens—some people move to the newly manned queues from nearby busy queues. In anticipation, people may prefer to line up in busy queues next to unmanned ones. Mathematically we discuss the problem of dynamic arrangement of the queues in a service system where at any time each server can be in either an active or an inactive mode. A balancing strategy determines how customers will be reallocated when a station becomes active. Given a balancing strategy, we seek a partition of customers to queues that minimizes the maximum wait time of a customer in each of the active stations, thereby keeping the system balanced at all times. We study two balancing strategies that we call Split and Trim. For the Split strategy we discuss a special case (the stations are ordered on a line and a single unmanned station is at one end). We show how an optimal partition can be calculated recursively. We then give partitions that approximate the minimal expected wait time within a factor of 1+O(1/N), under each of these strategies, where N is the number of stations. We obtain similar bounds (to within factor 2) for the case, where the number of active servers can be any 1⩽n⩽N−1, and the balancing strategy is Trim.

Details DOI

TCS Journal 1991 Journal Article

Learnability with respect to fixed distributions

Gyora M. Benedek
Alon Itai

Valiant's protocol for learning is extended to the case where the distribution of the examples is known to the learner. Namely, the notion of a concept class C being learnable with respect to distribution D is defined and the learnable pairs (C, D) of concept classes C and distributions D are characterized. Another notion is the existence of a finite cover for C with respect to D. The main result is that C is learnable with respect to D if and only if C is finitely coverable with respect to D. The size of the cover is then related to the Vapnik-Chervonenkis dimension. An additional property of the learning method is robustness, i. e. , learning succeeds even if part of the input is erroneous. It is also shown that if D is discrete then every concept class is learnable with respect to D. The main concern of the paper is the number of examples sufficient to probabilistically identify (or approximate) a concept — not the time needed to compute it. Indeed, in some cases the function which associates a sample with a hypothesis is undecidable, and even if it is computable, the computation may be infeasible. The computational complexity of the algorithms used for learning are considered only for discrete distributions.

Details DOI

I&C Journal 1990 Journal Article

Symmetry breaking in distributed networks

Alon Itai
Michael Rodeh

Given a ring of n processors it is required to design the processors such that they will be able to choose a leader (a uniquely designated processor) by sending messages along the ring. If the processors are indistinguishable then there exists no deterministic algorithm to solve the problem. To overcome this difficulty, probabilistic algorithms are proposed. The algorithms may run forever but they terminate within finite time on the average. For the synchronous case several algorithms are presented: The simplest requires, on the average, the transmission of no more than 2. 442n bits and O(n) time. More sophisticated algorithms trade time for communication complexity. If the processors work asynchronously then on the average O(n log n) bits are transmitted. In the above cases the size of the ring is assumed to be known to all the processors. If the size is not known then finding it may be be done only with high probability: any algorithm may yield incorrect results (with nonzero probability) for some values of n. Another difficulty is that, if we insist on correctness, the processors may not explicity terminate. Rather, the entire ring reaches an inactive state, in which no processor initiates communication.

Details DOI

I&C Journal 1988 Journal Article

The multi-tree approach to reliability in distributed networks

Alon Itai
Michael Rodeh

Consider a network of asynchronous processors communicating by sending messages over unreliable lines. There are many advantages to restricting all communications to a spanning tree. To overcome the possible failure of k′ < k edges, we describe a communication protocol which uses k rooted spanning trees having the property that for every vertex ν the paths from ν to the root are edge-disjoint. An algorithm to find two such trees in a 2-edge connected graph is described that runs in time proportional in the number of edges in the graph. This algorithm has a distributed version which finds the two trees even when a single edge fails during their construction. The two trees then may be used to transform certain centralized algorithms to distributed, reliable, and efficient ones.

Details DOI

FOCS Conference 1984 Conference Paper

The Multi-Tree Approach to Reliability in Distributed Networks

Alon Itai
Michael Rodeh

Consider a network of asynchronous processors communicating by sending messages over unreliable lines. There are many advantages to restrict all communications to a spanning tree. To overcome the possible failure of k<k edges, we describe a communication protocol which uses k rooted spanning trees having the property that for every vertex v the paths from v to the root are edge-disjoint. A linear algorithm to find two such trees in a 2 edge-connected graph is described. This algorithm has a distributed version which finds the two trees even when a single edge fails during their construction. Finally, a method is given to transform centralized algorithms to distributed, reliable and efficient ones.

Details

FOCS Conference 1981 Conference Paper

Symmetry Breaking in Distributive Networks

Alon Itai
Michael Rodeh

Given a ring (cycle) of n processes it is required to design the processes so that they will be able to choose a leader (a uniquely designated process) by sending messages along the ring. If the processes are indistiguishable there is no deterministic algorithm, and therefore probabilistic algorithms are proposed. These algorithms need not terminate, but their expected complexity (time or number of bits of communication) is bounded by a function of n. If the processes work asynchronously then on the average O(n log2n) bits are transmitted. In the above cases the size n of the ring was assumed to be known. If n is not known it is suggested first to determine the value of n and then use the above algorithm. However, n may only be determined probabilistically and any algorithm may yield an incorrect value. In addition, it is shown that the size of the ring cannot be calculated by any probabilistic algorithm in which the processes can sense termination.

Details

STOC Conference 1977 Conference Paper

Finding a Minimum Circuit in a Graph

Alon Itai

Finding minimum circuits in graphs and digraphs is discussed. An almost minimum circuit is a circuit which may have only one edge more than the minimum. An 0(n 2 ) algorithm is presented to find an almost minimum circuit. The straightforward algorithm for finding a minimum circuit has an 0(ne) behavior. It is refined to yield an 0(n 2 ) average time algorithm. An alternative method is to reduce the problem of finding a minimum circuit to that of finding a triangle in an auxiliary graph. Three methods for finding a triangle in a graph are presented. The first has an 0(e 3/2 ) worst case bound ( (n) for planar graphs); the second takes 0(n 5/3 ) time on the average; the third has an 0(n log7 ) worst case behavior. For digraphs, recent results of Bloniarz, Fisher and Meyer are used to obtain an algorithm with 0(n 2 logn) average behavior.

Details

FOCS Conference 1975 Conference Paper

On the Complexity of Timetable and Multi-Commodity Flow Problems

Shimon Even
Alon Itai
Adi Shamir

A very primitive version of Gotlieb's timetable problem is shown to be NP-complete, and therefore all the common timetable problems are NP-complete. A polynomial time algorithm, in case all teachers are binary, is shown. The theorem that a meeting function always exists if all teachers and classes have no time constraints is proved. The multi-commodity integral flow problem is shown to be NP-complete even if the number of commodities is two. This is true both in the directed and undirected cases. Finally, the two commodity real flow problem in undirected graphs is shown to be solvable in polynomial time. The time bound is O(|v|2|E|).

Details