Arrow Research search

Author name cluster

Yuval Rabani

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.

54 papers
2 author rows

Possible papers

54

SODA Conference 2023 Conference Paper

Generalized Unrelated Machine Scheduling Problem

  • Shichuan Deng
  • Jian Li 0015
  • Yuval Rabani

We study the generalized load-balancing (GLB) problem, where we are given n jobs, each of which needs to be assigned to one of m unrelated machines with processing times { p ij }. Under a job assignment σ, the load of each machine i is Ψ i ( p i [σ]) where ψ i: ℝ n → ℝ ≥0 is a symmetric monotone norm and p i [σ] is the n - dimensional vector { p ij · 𝕀 [σ( j ) = i ]} j∈[n]. Our goal is to minimize the generalized makespan ø(load(σ)), where φ: ℝ m → ℝ ≥0 is another symmetric monotone norm and load(σ) is the m -dimensional machine load vector. This problem significantly generalizes many classic optimization problems, e. g. , makespan minimization, set cover, minimum-norm load-balancing, etc. We also study the special case of identical machine scheduling, i. e. , P ij = p j for all machine i. Our main result is a polynomial time randomized algorithm that achieves an approximation factor of O (log n ), matching the lower bound of set cover (which is special case of GLB) up to constant factor. We achieve this by rounding a novel configuration LP relaxation with exponential number of variables. To approximately solve the configuration LP, we design an approximate separation oracle for its dual program. In particular, the separation oracle can be reduced to the norm minimization with a linear constraint (NormLin) problem and we devise a polynomial time approximation scheme (PTAS) for it, which may be of independent interest. We also obtain constant factor approximation algorithms for some special cases.

Details

STOC Conference 2023 Conference Paper

The Randomized k-Server Conjecture Is False!

  • Sébastien Bubeck
  • Christian Coester
  • Yuval Rabani

We prove a few new lower bounds on the randomized competitive ratio for the k -server problem and other related problems, resolving some long-standing conjectures. In particular, for metrical task systems (MTS) we asympotically settle the competitive ratio and obtain the first improvement to an existential lower bound since the introduction of the model 35 years ago (in 1987).

Details

FOCS Conference 2022 Conference Paper

Shortest Paths without a Map, but with an Entropic Regularizer

  • Sébastien Bubeck
  • Christian Coester
  • Yuval Rabani

In a 1989 paper titled “shortest paths without a map”, Papadimitriou and Yannakakis introduced an online model of searching in a weighted layered graph for a target node, while attempting to minimize the total length of the path traversed by the searcher. This problem, later called layered graph traversal, is parametrized by the maximum cardinality k of a layer of the input graph. It is an online setting for dynamic programming, and it is known to be a rather general and fundamental model of online computing, which includes as special cases other acclaimed models. The deterministic competitive ratio for this problem was soon discovered to be exponential in k, and it is now nearly resolved: it lies between $\Omega(2^{k})$ and $O(k2^{k})$. Regarding the randomized competitive ratio, in 1993 Ramesh proved, surprisingly, that this ratio has to be at least $\Omega(k^{2}/log^{1+\varepsilon}k)$ (for any constant $\varepsilon\gt0)$. In the same paper, Ramesh also gave an $O(k^{13})$-competitive randomized online algorithm. Since 1993, no progress has been reported on the randomized competitive ratio of layered graph traversal. In this work we show how to apply the mirror descent framework on a carefully selected evolving metric space, and obtain an $O(k^{2})$ competitive randomized online algorithm, nearly matching the known lower bound on the randomized competitive ratio.

Details

SODA Conference 2021 Conference Paper

Online Multiserver Convex Chasing and Optimization

  • Sébastien Bubeck
  • Yuval Rabani
  • Mark Sellke

We introduce the problem of k -chasing of convex functions, a simultaneous generalization of both the famous k -server problem in ℝ d, and of the problem of chasing convex bodies and functions. Aside from fundamental interest in this general form, it has natural applications to online k -clustering problems with objectives such as k -median or k -means. We show that this problem exhibits a rich landscape of behavior. In general, if both k > 1 and d > 1 there does not exist any online algorithm with bounded competitiveness. By contrast, we exhibit a class of nicely behaved functions (which include in particular the above-mentioned clustering problems), for which we show that competitive online algorithms exist, and moreover with dimension-free competitive ratio. We also introduce a parallel question of top- k action regret minimization in the realm of online convex optimization. There, too, a much rougher landscape emerges for k > 1. While it is possible to achieve vanishing regret, unlike the top-one action case the rate of vanishing does not speed up for strongly convex functions. Moreover, vanishing regret necessitates both intractable computations and randomness. Finally we leave open whether almost dimension-free regret is achievable for k > 1 and general convex losses. As evidence that it might be possible, we prove dimension-free regret for linear losses via an information-theoretic argument.

Details

SODA Conference 2017 Conference Paper

Matrix Balancing in L p Norms: Bounding the Convergence Rate of Osborne's Iteration

  • Rafail Ostrovsky
  • Yuval Rabani
  • Arman Yousefi

We study an iterative matrix conditioning algorithm due to Osborne (1960). The goal of the algorithm is to convert a square matrix into a balanced matrix where every row and corresponding column have the same norm. The original algorithm was proposed for balancing rows and columns in the L 2 norm, and it works by iterating over balancing a row-column pair in fixed round-robin order. Variants of the algorithm for other norms have been heavily studied and are implemented as standard preconditioners in many numerical linear algebra packages. Recently, Schulman and Sinclair (2015), in a first result of its kind for any norm, analyzed the rate of convergence of a variant of Osborne's algorithm that uses the L ∞ norm and a different order of choosing row-column pairs. In this paper we study matrix balancing in the L 1 norm and other L p norms. We show the following results for any matrix, resolving in particular a main open problem mentioned by Schulman and Sinclair. 1. We analyze the iteration for the L 1 norm under a greedy order of balancing. We show that it converges to an ∊-balanced matrix in K = O (min{ ∊ −2 log w, ∊ −1 n 3/2 log(w / ∊)}) iterations that cost a total of O ( m + Kn log n ) arithmetic operations over O ( n log(w/∊))-bit numbers. Here m is the number of non-zero entries of A, and w =∑ i, j |aij|/a min with a min = min{|a ij |: aj ≠ 0}. 2. We show that the original round-robin implementation converges to an ∊ -balanced matrix in O (∊ −2 n 2 log w) iterations totaling O (∊ −2 mn log w ) arithmetic operations over O ( n log( w / ∊ ))-bit numbers. 3. We show that a random implementation of the iteration converges to an ∊ -balanced matrix in O ( ∊ −2 log w ) iterations using O ( m + ∊ −2 n log w ) arithmetic operations over O (log( wn / ∊ ))-bit numbers. 4. We demonstrate a lower bound of on the convergence rate of any implementation of the iteration. 5. We observe, through a known trivial reduction, that our results for L 1 balancing apply to any L p norm for all finite p, at the cost of increasing the number of iterations by only a factor of p. We note that our techniques are very different from those used by Schulman and Sinclair.

Details

STOC Conference 2015 Conference Paper

Learning Arbitrary Statistical Mixtures of Discrete Distributions

  • Jian Li 0015
  • Yuval Rabani
  • Leonard J. Schulman
  • Chaitanya Swamy

We study the problem of learning from unlabeled samples very general statistical mixture models on large finite sets. Specifically, the model to be learned, mix, is a probability distribution over probability distributions p, where each such p is a probability distribution over [n] = {1,2,...,n}. When we sample from mix, we do not observe p directly, but only indirectly and in very noisy fashion, by sampling from [n] repeatedly, independently K times from the distribution p. The problem is to infer mix to high accuracy in transportation (earthmover) distance.

Details

FOCS Conference 2013 Conference Paper

An optimal randomized online algorithm for reordering buffer management

  • Noa Avigdor-Elgrabli
  • Yuval Rabani

We give an Õ (log log k)-competitive randomized online algorithm for reordering buffer management, where k is the buffer size. Our bound matches the lower bound of Adamaszek et al. (STOC 2011). Our algorithm has two stages which are executed online in parallel. The first stage computes deterministically a feasible fractional solution to an LP relaxation for reordering buffer management. The second stage "rounds" using randomness the fractional solution. The first stage is based on the online primal-dual schema, combined with a dual fitting charging scheme. As primal-dual steps and dual fitting steps are interleaved and in some sense conflicting, combining them is challenging. We also note that we apply the primal-dual schema to a relaxation with mixed packing and covering constraints. The first stage produces a fractional LP solution with cost within a factor of Õ (log log k) of the optimal LP cost. The second stage is an online algorithm that converts any LP solution to an integral solution, while increasing the cost by a constant factor. This stage generalizes recent results that gave a similar approximation guarantee using an offline rounding algorithm.

Details

STOC Conference 2006 Conference Paper

On earthmover distance, metric labeling, and 0-extension

  • Howard J. Karloff
  • Subhash Khot
  • Aranyak Mehta
  • Yuval Rabani

We study the fundamental classification problems O-EXTENSION and METRIC LABELING. MINIMUM WEIGHT TRIANGULATION is closely related to partitioning problems in graph theory and to Lipschitz extensions in Banach spaces; its generalization METRIC LABELING is motivated by applications in computer vision. Researchers had proposed using earthmover metrics to get polynomial time-solvable relaxations for these problems. A conjecture that has attracted much attention recently is that the integrality ratio for these relaxations is constant.We prove that the integrality ratio of the earthmover relaxation for METRIC LABELING is Ω(log n) (which is asymptotically tight), k being the number of labels, whereas the best previous lower bound on the integrality ratio was only constant; that the integrality ratio of the earthmover relaxation for O-EXTENSION is Ω(√log k), k being the number of terminals (it was known to be O((log k)/log log k)), whereas the best previous lower bound was only constant; that for no ε>0 is there a polynomial-time O((log n) 1/4-ε )-approximation algorithm for O-EXTENSION, n being the number of vertices, unless NP ⊆ DTIME(n poly(log n) ), whereas the strongest inapproximability result known before was only MAX SNP-hardness; and that there is a polynomial-time approximation algorithm for O-EXTENSION with performance ratio O(√diam(d)), where diam(d) is the ratio of the largest to smallest nonzero distances in the terminal metric.

Details

FOCS Conference 2006 Conference Paper

The Effectiveness of Lloyd-Type Methods for the k-Means Problem

  • Rafail Ostrovsky
  • Yuval Rabani
  • Leonard J. Schulman
  • Chaitanya Swamy

We investigate variants of Lloyd's heuristic for clustering high dimensional data in an attempt to explain its popularity (a half century after its introduction) among practitioners, and in order to suggest improvements in its application. We propose and justify a clusterability criterion for data sets. We present variants of Lloyd's heuristic that quickly lead to provably near-optimal clustering solutions when applied to well-clusterable instances. This is the first performance guarantee for a variant of Lloyd's heuristic. The provision of a guarantee on output quality does not come at the expense of speed: some of our algorithms are candidates for being faster in practice than currently used variants of Lloyd's method. In addition, our other algorithms are faster on well-clusterable instances than recently proposed approximation algorithms, while maintaining similar guarantees on clustering quality. Our main algorithmic contribution is a novel probabilistic seeding process for the starting configuration of a Lloyd-type iteration

Details

FOCS Conference 2005 Conference Paper

Error-Correcting Codes for Automatic Control

  • Rafail Ostrovsky
  • Yuval Rabani
  • Leonard J. Schulman

In many control-theory applications one can classify all possible states of the device by an infinite state graph with polynomially-growing expansion. In order for a controller to control or estimate the state of such a device, it must receive reliable communications from its sensors; if there is channel noise, the encoding task is subject to a stringent real-time constraint. We show a constructive on-line error correcting code that works for this class of applications. Our code is computationally efficient and enables on-line estimation and control in the presence of channel noise. It establishes a constructive (and optimal-within-constants) analog, for control applications, of the Shannon coding theorem.

Details

STOC Conference 2005 Conference Paper

Low distortion embeddings for edit distance

  • Rafail Ostrovsky
  • Yuval Rabani

We show that 0,1 d endowed with edit distance embeds into l 1 with distortion 2 O (√log d log log d ). We further show efficient implementations of the embedding that yield solutions to various computational problems involving edit distance. These include sketching, communication complexity, nearest neighbor search. For all these problems, we improve upon previous bounds.

Details

STOC Conference 2004 Conference Paper

Low distortion maps between point sets

  • Claire Mathieu
  • Yuval Rabani
  • Alistair Sinclair

We initiate the study of the minimum distortion problem: given as input two n-point metric spaces, find a bijection between them with minimum distortion. This is an abstraction of certain geometric problems in shape and image matching, and is also a natural variation and extension of the fundamental problems of graph isomorphism and bandwidth. Our focus is on algorithms that find an optimal (or near-optimal) bijection when the distortion is fairly small. We present a polynomial time algorithm that finds an optimal bijection between two line metrics, provided the distortion is less than 3+2√2. We also give a parameterized polynomial time algorithm that finds an optimal bijection between an arbitrary unweighted graph metric and a bounded-degree tree metric.

Details

STOC Conference 2003 Conference Paper

Approximation schemes for clustering problems

  • Wenceslas Fernandez de la Vega
  • Marek Karpinski
  • Claire Mathieu
  • Yuval Rabani

Let k be a fixed integer. We consider the problem of partitioning an input set of points endowed with a distance function into k clusters. We give polynomial time approximation schemes for the following three clustering problems: Metric k -Clustering, l 2 2 k -Clustering, and l 2 2 k -Median. In the k -Clustering problem, the objective is to minimize the sum of all intra-cluster distances. In the k -Median problem, the goal is to minimize the sum of distances from points in a cluster to the (best choice of) cluster center. In metric instances, the input distance function is a metric. In l 2 2 instances, the points are in R d and the distance between two points x,y is measured by x−y 2 2 (notice that (R d , ⋅ 2 2 is not a metric space). For the first two problems, our results are the first polynomial time approximation schemes. For the third problem, the running time of our algorithms is a vast improvement over previous work.

Details

STOC Conference 2003 Conference Paper

Cell-probe lower bounds for the partial match problem

  • T. S. Jayram
  • Subhash Khot
  • Ravi Kumar 0001
  • Yuval Rabani

Given a database of n points in (0,1) d , the partial match problem is: In response to a query x in (0, 1, *) d , find a database point y such that for every i whenever x i ≠ *, we have x i = y i . In this paper we show randomized lower bounds in the cell-probe model for this well-studied problem[18, 11, 19, 16, 4, 6 ].Our lower bounds follow from a two-party asymmetric randomized communication complexity near-optimal lower bound for this problem, where we show that either Alice has to send Ω(d log n) bits or Bob has to send Ω(n 1 - o(1) ) bits. When applied to the cell-probe model, it means that if the number of cells is restricted to be poly(n, d) where each cell is of size poly(log n, d), then Ω(d/log 2 n) probes are needed. This is an exponential improvement over the previously known lower bounds for this problem[16, 4].

Details

FOCS Conference 2001 Conference Paper

Approximating Directed Multicuts

  • Joseph Cheriyan
  • Howard J. Karloff
  • Yuval Rabani

The seminal paper of F. T. Leighton and S. Rao (1988) and subsequent papers presented approximate min-max theorems relating multicommodity flow values and cut capacities in undirected networks, developed the divide-and-conquer method for designing approximation algorithms, and generated novel tools for utilizing linear programming relaxations. Yet, despite persistent research efforts, these achievements could not be extended to directed networks, excluding a few cases that are "symmetric" and therefore similar to undirected networks. The paper is an attempt to remedy the situation. We consider the problem of finding a minimum multicut in a directed multicommodity flow network, and give the first nontrivial upper bounds on the maxflow-to-min multicut ratio. Our results are algorithmic, demonstrating nontrivial approximation guarantees.

Details

STOC Conference 2001 Conference Paper

Approximation algorithms for constrained for constrained node weighted steiner tree problems

  • Anna Moss
  • Yuval Rabani

We consider a class of optimization problems, where the input is an undirected graph with two weight functions defined for each node, namely the node's profit and its cost . The goal is to find a connected set of nodes of low cost and high profit. We present approximation algorithms for three natural optimization criteria that arise in this context, all of which are NP-hard. The budget problem asks for maximizing the profit of the set subject to a budget constraint on its cost. The quota problem requires minimizing the cost of the set subject to a quota constraint on its profit. Finally, the prize collecting problem calls for minimizing the cost of the set plus the profit (here interpreted as a penalty) of the complement set. For all three problems, our algorithms give an approximation guarantee of O(\log n) , where n is the number of nodes. To the best of our knowledge, these are the first approximation results for the quota problem and for the prize collecting problem, both of which are at least as hard to approximate as set cover. For the budget problem, our results improve on a previous O(\log^2 n) result of Guha, Moss, Naor, and Schieber. Our methods involve new theorems relating tree packings to (node) cut conditions. We also show similar theorems (with better bounds) using edge cut conditions. These imply bounds for the analogous budget and quota problems with edge costs which are comparable to known (constant factor) bounds.

Details

FOCS Conference 2001 Conference Paper

Approximation Algorithms for the Job Interval Selection Problem and Related Scheduling Problems

  • Julia Chuzhoy
  • Rafail Ostrovsky
  • Yuval Rabani

The authors consider the job interval selection problem (JISP), a simple scheduling model with a rich history and numerous applications. Special cases of this problem include the so-called real-time scheduling problem (also known as the throughput maximization problem) in single and multiple machine environments. In these special cases we have to maximize the number of jobs scheduled between their release date and deadline (preemption is not allowed). Even the single machine case is NP-hard. The unrelated machines case, as well as other special cases of JISP, are MAX SNP-hard. A simple greedy algorithm gives a 2-approximation for JISP. Despite many efforts, this was the best approximation guarantee known, even for throughput maximization on a single machine. The authors break this barrier and show an approximation guarantee of less than 1. 582 for arbitrary instances of JISP. For some special cases, we show better results. Our methods can be used to give improved bounds for some related resource allocation problems that were considered recently in the literature.

Details

FOCS Conference 2000 Conference Paper

Polynomial Time Approximation Schemes for Geometric k-Clustering

  • Rafail Ostrovsky
  • Yuval Rabani

We deal with the problem of clustering data points. Given n points in a larger set (for example, R/sup d/) endowed with a distance function (for example, L/sup 2/ distance), we would like to partition the data set into k disjoint clusters, each with a "cluster center", so as to minimize the sum over all data points of the distance between the point and the center of the cluster containing the point. The problem is provably NP-hard in some high dimensional geometric settings, even for k=2. We give polynomial time approximation schemes for this problem in several settings, including the binary cube (0, 1)/sup d/ with Hamming distance, and R/sup d/ either with L/sup 1/ distance, or with L/sup 2/ distance, or with the square of L/sup 2/ distance. In all these settings, the best previous results were constant factor approximation guarantees. We note that our problem is similar in flavor to the k-median problem (and the related facility location problem), which has been considered in graph-theoretic and fixed dimensional geometric settings, where it becomes hard when k is part of the input. In contrast, we study the problem when k is fixed, but the dimension is part of the input. Our algorithms are based on a dimension reduction construction for the Hamming cube, which may be of independent interest.

Details

FOCS Conference 1999 Conference Paper

Fairness in Routing and Load Balancing

  • Jon M. Kleinberg
  • Yuval Rabani
  • Éva Tardos

We consider the issue of network routing subject to explicit fairness conditions. The optimization of fairness criteria interacts in a complex fashion with the optimization of network utilization and throughput; in this work, we undertake an investigation of this relationship through the framework of approximation algorithms. In this work we consider the problem of selecting paths for routing so as to provide a bandwidth allocation that is as fair as possible (in the max-min sense). We obtain the first approximation algorithms for this basic optimization problem, for single-source unsplittable routings in an arbitrary directed graph. Special cases of our model include several fundamental load balancing problems, endowing them with a natural fairness criterion to which our approach can be applied. Our results form an interesting counterpart to the work of Megiddo (1974), who considered max-min fairness for single-source fractional flow. The optimization problems in our setting become NP-complete, and require the development of new techniques for relating fractional relaxations of routing to the equilibrium constraints imposed by the fairness criterion.

Details

FOCS Conference 1998 Conference Paper

Local Divergence of Markov Chains and the Analysis of Iterative Load Balancing Schemes

  • Yuval Rabani
  • Alistair Sinclair
  • Rolf Wanka

We develop a general technique for the quantitative analysis of iterative distributed load balancing schemes. We illustrate the technique by studying two simple, intuitively appealing models that are prevalent in the literature: the diffusive paradigm, and periodic balancing circuits (or the dimension exchange paradigm). It is well known that such load balancing schemes can be roughly modeled by Markov chains, but also that this approximation can be quite inaccurate. Our main contribution is an effective way of characterizing the deviation between the actual loads and the distribution generated by a related Markov chain, in terms of a natural quantity which we call the local divergence. We apply this technique to obtain bounds on the number of rounds required to achieve coarse balancing in general networks, cycles and meshes in these models. For balancing circuits, we also present bounds for the stronger requirement of perfect balancing, or counting.

Details

FOCS Conference 1996 Conference Paper

Path Coloring on the Mesh

  • Yuval Rabani

In the minimum path coloring problem, we are given a list of pairs of vertices of a graph. We are asked to connect each pair by a colored path. Paths of the same color must be edge disjoint. Our objective is to minimize the number of colors used. This problem was raised by A. Aggarwal et al. (1994) and P. Raghavan and E. Upfal (1994) as a model for routing in all-optical networks. It is also related to questions in circuit routing. In this paper, we improve the O(ln N) approximation result of J. Kleinberg and E. Tardos (1995) for path coloring on the N/spl times/N mesh. We give an O(1) approximation algorithm to the number of colors needed, and a poly(ln ln N) approximation algorithm to the choice of paths and colors. To the best of our knowledge, these are the first sub-logarithmic bounds for any network other than trees, rings, or trees of rings. Our results are based on developing new techniques for randomized rounding. These techniques iteratively improve a fractional solution until it approaches integrality. They are motivated by the method used by F. T. Leighton, B. M. Maggs, and S. B. Rao (1994) for packet routing.

Details

FOCS Conference 1994 Conference Paper

On-line Admission Control and Circuit Routing for High Performance Computing and Communication

  • Baruch Awerbuch
  • Rainer Gawlick
  • Frank Thomson Leighton
  • Yuval Rabani

This paper considers the problems of admission control and virtual circuit routing in high performance computing and communication systems. Admission control and virtual circuit routing problems arise in numerous applications, including video-servers, real-lime database servers, and the provision of permanent virtual channel in large-scale communications networks. The paper describes both upper and lower bounds on the competitive ratio of algorithms for admission control and virtual circuit routing in trees, arrays, and hypercubes (the networks most commonly used in conjunction with nigh performance computing and communication). Our results include optimal algorithms for admission control and virtual circuit routing in trees, as well as the first competitive algorithms for these problems on non-tree networks. A key result of our research is the development of on-line algorithms that substantially outperform the greedy-based approaches that are used in practice. >

Details

FOCS Conference 1993 Conference Paper

On the Value of Information in Coordination Games (preliminary version)

  • Sandy Irani
  • Yuval Rabani

We discuss settings where several "agents" combine efforts to solve problems. This is a well-known setting in distributed artificial intelligence. Our work addresses theoretical questions in this model which are motivated by the work of X. Deng and C. H. Papadimitriou (1992). We consider optimization problems, in particular load balancing and virtual circuit routing, in which the input is divided among the agents. An underlying directed graph, whose nodes are the agents, defines the constraints on the information each agent may have about the portion of the input held by other agents. The questions we discuss are: Given a bound on the maximum out-degree in this graph, which is the best graph? What is the quality of the solution obtained as a function of the maximum out-degree? . >

Details

FOCS Conference 1992 Conference Paper

A Decomposition Theorem and Bounds for Randomized Server Problems

  • Avrim Blum
  • Howard J. Karloff
  • Yuval Rabani
  • Michael E. Saks

The authors prove a lower bound of Omega ( square root logk/loglogk) for the competitive ratio of randomized algorithms for the k-server problem against an oblivious adversary. The bound holds for arbitrary metric spaces (of at least k+1 points) and provides a new lower bound for the metrical task system problem as well. This improves the previous best lower bound of Omega (loglogk) for arbitrary metric spaces, more closely approaching the conjectured lower bound of Omega (logk). They also prove a lower bound of Omega (/sup logk///sub loglogk/) for the server problem on k+1 equally-spaced points on a line, which corresponds to some natural motion-planning problems. >

Details

FOCS Conference 1991 Conference Paper

Competitive Algorithms for Layered Graph Traversal

  • Amos Fiat
  • Dean P. Foster
  • Howard J. Karloff
  • Yuval Rabani
  • Yiftach Ravid
  • Sundar Vishwanathan

A layered graph is a connected, weighted graph whose vertices are partitioned into sets L/sub 0/=(s), L/sub 1/, L/sub 2/, .. ., and whose edges run between consecutive layers. Its width is max( mod L/sub i/ mod ). In the online layered graph traversal problem, a searcher starts at s in a layered graph of unknown width and tries to reach a target vertex t; however, the vertices in layer i and the edges between layers i-1 and i are only revealed when the searcher reaches layer i-1. The authors give upper and lower bounds on the competitive ratio of layered graph traversal algorithms. They give a deterministic online algorithm that is O(9w)-competitive on width-w graphs and prove that for no w can a deterministic online algorithm have a competitive ratio better than 2w/sup -2/ on width-w graphs. They prove that for all w, w/2 is a lower bound on the competitive ratio of any randomized online layered graph traversal algorithm. For traversing layered graphs consisting of w disjoint paths tied together at a common source, they give a randomized online algorithm with a competitive ratio of O(log w) and prove that this is optimal up to a constant factor. >

Details

FOCS Conference 1990 Conference Paper

Competitive k-Server Algorithms (Extended Abstract)

  • Amos Fiat
  • Yuval Rabani
  • Yiftach Ravid

Deterministic competitive k-server algorithms are given for all k and all metric spaces. This settles the k-server conjecture of M. S. Manasse et al. (1988) up to the competitive ratio. The best previous result for general metric spaces was a three-server randomized competitive algorithm and a nonconstructive proof that a deterministic three-server competitive algorithm exists. The competitive ratio the present authors can prove is exponential in the number of servers. Thus, the question of the minimal competitive ratio for arbitrary metric spaces is still open. The methods set forth here also give competitive algorithms for a natural generalization of the k-server problem, called the k-taxicab problem. >

Details
v2026.09.13