Arrow Research search

Author name cluster

Orli Waarts

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.

16 papers
1 author row

Possible papers

16

FOCS Conference 1996 Conference Paper

Efficient Information Gathering on the Internet (extended abstract)

  • Oren Etzioni
  • Steve Hanks
  • Tao Jiang 0001
  • Richard M. Karp
  • Omid Madani
  • Orli Waarts

The Internet offers unprecedented access to information. At present most of this information is free, but information providers ore likely to start charging for their services in the near future. With that in mind this paper introduces the following information access problem: given a collection of n information sources, each of which has a known time delay, dollar cost and probability of providing the needed information, find an optimal schedule for querying the information sources. We study several variants of the problem which differ in the definition of an optimal schedule. We first consider a cost model in which the problem is to minimize the expected total cost (monetary and time) of the schedule, subject to the requirement that the schedule may terminate only when the query has been answered or all sources have been queried unsuccessfully. We develop an approximation algorithm for this problem and for an extension of the problem in which more than a single item of information is being sought. We then develop approximation algorithms for a reward model in which a constant reward is earned if the information is successfully provided, and we seek the schedule with the maximum expected difference between the reward and a measure of cost. The monetary and time costs may either appear in the cost measure or be constrained not to exceed a fixed upper bound; these options give rise to four different variants of the reward model.

Details

FOCS Conference 1995 Conference Paper

Competitive Access Time via Dynamic Storage Rearrangement (Preliminary Version)

  • Amos Fiat
  • Yishay Mansour
  • Adi Rosén
  • Orli Waarts

We model the problem of storing items in some warehouse (modeled as an undirected graph) where a server has to visit items over time, with the goal of minimizing the total distance traversed by the server. Special cases of this problem include the management of a real industrial stacker crane warehouse, automatic robot run warehouses, disk track optimization to minimize access time, managing two dimensional memory (bubble memory and mass storage systems), doubly linked list management, and the process migration problem. The static version of this problem assumes some known probability distribution on the access patterns. We initiate the study of the dynamic version of the problem, where the robot may rearrange the warehouse to deal efficiently with future events. We require no statistical assumptions on the access pattern, and give competitive algorithms that rearrange the warehouse over time to deal efficiently with the true access patterns. We give non-trivial upper bounds for the general problem, along with some interesting lower bounds. In addition, we model realistic data access patterns on disk storage by considering two practically significant scenarios: access to some database via dynamically changing alternative indices and access patterns derived from root to leaf traversals of some (unknown) tree structure. In both cases we give greatly improved competitive ratios.

Details

FOCS Conference 1995 Conference Paper

Improved Algorithms and Analysis for Secretary Problems and Generalizations

  • Miklós Ajtai
  • Nimrod Megiddo
  • Orli Waarts

In the classical secretary problem, n objects from an ordered set arrive in random order, and one has to accept k of them so that the final decision about each object is made only on the basis of its rank relative to the ones already seen. Variants of the problem depend on the goal: either maximize the probability of accepting the best k objects, or minimize the expectation of the sum of the ranks (or powers of ranks) of the accepted objects. The problem and its generalizations are at the core of tasks with a large data set, in which it may be impractical to backtrack and select previous choices. Optimal algorithms for the special case of k=1 are well known. Partial solutions for the first variant with general k are also known. In contrast, an explicit solution for the second variant with general k has not been known; even the question of whether or not the expected sum of powers of the ranks of selected items tends to infinity with n has been unresolved. We answer these open questions by obtaining explicit algorithms. For each z/spl ges/1, the resulting expected sum of the zth powers of the ranks of the selected objects is at most k/sup z+1//(z+1)+C(z)/spl middot/k/sup z+0. 5/log k, whereas the best possible value at all is k/sup z+1//(z+1)+O(k/sup z/). Our methods are very intuitive and apply to some generalizations. We also derive a lower bound on the trade-off between the probability of selecting the best object and its expected rank.

Details

FOCS Conference 1995 Conference Paper

The Bit Vector Intersection Problem (Preliminary Version)

  • Richard M. Karp
  • Orli Waarts
  • Geoffrey Zweig

This paper introduces the bit vector intersection problem: given a large collection of sparse bit vectors, find all the pairs with at least t ones in common for a given input parameter t. The assumption is that the number of ones common to any two vectors is significantly less than t, except for an unknown set of O(n) pairs. This problem has important applications in DNA physical mapping, clustering, and searching for approximate dictionary matches. We present two randomized algorithms that solve this problem with high probability and in sub-quadratic expected time. One of these algorithms is based on a recursive tree-searching procedure, and the other on hashing. We analyze the tree scheme in terms of branching processes, while our analysis of the hashing scheme is based on Markov chains. Since both algorithms have similar asymptotic performance, we also examine experimentally their relative merits in practical situations. We conclude by showing that a fundamental problem arising in the Human Genome Project is captured by the bit vector intersection problem described above and hence can be solved by our algorithms.

Details

FOCS Conference 1994 Conference Paper

A Theory of Competitive Analysis for Distributed Algorithms

  • Miklós Ajtai
  • James Aspnes
  • Cynthia Dwork
  • Orli Waarts

We introduce a theory of competitive analysis for distributed algorithms. The first steps in this direction were made in the seminal papers of Y. Bartal et al. (1992), and of B. Awerbuch et al. (1992), in the context of data management and job scheduling. In these papers, as well as in other subsequent sequent work, the cost of a distributed algorithm is compared to the cost of an optimal global-control algorithm. In this paper we introduce a more refined notion of competitiveness for distributed algorithms, one that reflects the performance of distributed algorithms more accurately. In particular, our theory allows one to compare the cost of a distributed on-line algorithm to the cost of an optimal distributed algorithm. We demonstrate our method by studying the cooperative collect primitive, first abstracted by M. Saks, N. Shavit, and H. Woll (1991). We provide the first algorithms that allow processes to cooperate to finish their work in fewer steps. Specifically, we present two algorithms (with different strengths), and provide a competitive analysis for each one. >

Details

FOCS Conference 1992 Conference Paper

Randomized Consensus in Expected O(n log ^2 n) Operations Per Processor

  • James Aspnes
  • Orli Waarts

The paper presents a new randomized algorithm for achieving consensus among asynchronous processors that communicate by reading and writing shared registers. The fastest previously known algorithm requires a processor to perform an expected O(n/sup 2/ log n) read and write operations in the worst case. In the algorithm, each processor executes at most an expected O(n log/sup 2/ n) read and write operations, which is close to the trivial lower bound of Omega (n). All previously known polynomial-time consensus algorithms were structured around a shared coin protocol in which each processor repeatedly adds random +or-1 votes to a common pool. Consequently, in all of these protocols, the worst case expected bound on the number of read and write operations done by a single processor is asymptotically no better than the bound on the total number of read and write operations done by all of the processors together. The authors succeed in breaking this tradition by allowing the processors to cast votes of increasing weights. This grants the adversary greater control since he can choose from up to n different weights (one for each processor) when determining the w i ht of the next vote to be cast. They prove that the shared coin protocol is correct nevertheless using martingale arguments. >

Details

FOCS Conference 1991 Conference Paper

Low Contention Linearizable Counting

  • Maurice Herlihy
  • Nir Shavit
  • Orli Waarts

The linearizable counting problem requires asynchronous concurrent processes to assign themselves successive values so that the order of the values assigned reflects the real-time order in which they were requested. It is shown that the problem can be solved without funneling all processes through a common memory location. Two new constructions for linearizable counting networks, data structures that solve the linearizable counting problem, are given. The first construction is nonblocking: some process takes a value after O(n) network gates have been traversed. The second construction is wait-free: it guarantees that each process takes a value after it traverses O(wn) gates, where w is a parameter affecting contention. It is shown that in any nonblocking or wait-free linearizable counting network, processes must traverse an average of Omega (n) gates, and so the constructions are close to optimal. A simpler and more efficient network is constructed by giving up the robustness requirements and allowing processes to wait for one another. >

Details

FOCS Conference 1990 Conference Paper

Perfectly Secure Message Transmission

  • Danny Dolev
  • Cynthia Dwork
  • Orli Waarts
  • Moti Yung

The problem of perfectly secure communication in a general network in which processors and communication lines may be faulty is studied. Lower bounds are obtained on the connectivity required for successful secure communication. Efficient algorithms that operate with this connectivity and rely on no complexity theoretic assumptions are derived. These are the first algorithms for secure communication in a general network to achieve simultaneously the goals of perfect secrecy, perfect resiliency, and a worst case time which is linear in the diameter of the network. >

Details

FOCS Conference 1988 Conference Paper

Coordinated Traversal: (t + 1)-Round Byzantine Agreement in Polynomial Time

  • Yoram Moses
  • Orli Waarts

The problem of efficiently performing Byzantine agreement in t+1 rounds in the face of arbitrarily malicious failures is treated. A communication-efficient polynomial-time protocol is presented for n>8t. The protocol is an early stopping protocol, halting in min(t+1, f+2) rounds in the worst case, where f is the number of processors that fail during the run. This is provably optimal. The protocol is based on a careful combination of early stopping, fault masking, and a technique called coordinated traversal. The combination of the three provides a powerful method for restricting the damage that a faulty processor, however malicious, can do. One of the byproducts of this protocol is a polynomial-time (t+1)-round protocol for the Byzantine firing squad problem. >

Details
v2026.09.13