Randomized competitive algorithms for the list update problem

We prove upper and lower bounds on the competitiveness of randomized algorithms for the list update problem of Sleator and Tarjan. We give a simple and elegant randomized algorithm that is more competitive than the best previous randomized algorithm due to Irani. Our algorithm uses randomness only during an initialization phase, and from then on runs completely deterministically. It is the first randomized competitive algorithm with this property to beat the deterministic lower bound. We generalize our approach to a model in which access costs are fixed but update costs are scaled by an arbitrary constantd. We prove lower bounds for deterministic list update algorithms and for randomized algorithms against oblivious and adaptive on-line adversaries. In particular, we show that for this problem adaptive on-line and adaptive off-line adversaries are equally powerful.A preliminary version of these results appeared in a joint paper with S. Irani in theProceedings of the 2nd Symposium on Discrete Algorithms, 1991 [17].This research was partially supported by NSF Grants CCR-8808949 and CCR-8958528.This research was partially supported by NSF Grant CCR-9009753.This research was supported in part by the National Science Foundation under Grant CCR-8658139, by DIMACS, a National Science Foundation Science and Technology center, Grant No. NSF-STC88-09648.     

Evolutionary algorithms and dynamic programming

Recently, it has been proven that evolutionary algorithms produce good results for a wide range of combinatorial optimization problems. Some of the considered problems are tackled by evolutionary algorithms that use a representation which enables them to construct solutions in a dynamic programming fashion. We take a general approach and relate the construction of such algorithms to the development of algorithms using dynamic programming techniques. Thereby, we give general guidelines on how to develop evolutionary algorithms that have the additional ability of carrying out dynamic programming steps. Finally, we show that for a wide class of the so-called DP-benevolent problems (which are known to admit FPTAS) there exists a fully polynomial-time randomized approximation scheme based on an evolutionary algorithm.     

Improving on-line construction of two-dimensional suffix trees for square matrices

The two-dimensional (2-D) suffix tree of an n×n square matrix A is a compacted trie that represents all square submatrices of A. We consider constructing 2-D suffix trees on-line, which means, instead of giving the whole matrix A in advance, A is separated and each part of A is given at different time as algorithms proceed. In general, developing an on-line algorithm is more difficult than developing an off-line algorithm. Moreover, the smaller the input grain size is, the harder it is to develop an on-line algorithm. In the case of 2-D suffix tree construction, dealing with a character at a time is harder than dealing with a row or a column at a time.In this paper we propose a randomized linear-time algorithm for constructing 2-D suffix trees on-line. This algorithm is superior to previous algorithms in two ways: (1) This is the first linear-time algorithm for constructing 2-D suffix trees on-line. Although there have been some linear-time algorithms for off-line construction, there were no linear-time algorithms for on-line construction. (2) We deal with the most fine-grain on-line case, i.e., our algorithm can construct a 2-D suffix tree even though only one character of A is given at a time, while previous on-line algorithms require at least a row and/or a column at a time.     

Combinatorial Algorithms for the Unsplittable Flow Problem

We provide combinatorial algorithms for the unsplittable flow problem (UFP) that either match or improve the previously best results. In the UFP we are given a (possibly directed) capacitated graph with n vertices and m edges, and a set of terminal pairs each with its own demand and profit. The objective is to connect a subset of the terminal pairs each by a single flow path subject to the capacity constraints such that the total profit of the connected pairs is maximized.We consider three variants of the problem. First is the classical UFP in which the maximum demand is at most the minimum edge capacity. It was previously known to have an O(√m) approximation algorithm; the algorithm is based on the randomized rounding technique and its analysis makes use of the Chernoff bound and the FKG inequality.We provide a combinatorial algorithm that achieves the same approximation ratio and whose analysis is considerably simpler. Second is the extended UFP in which some demands might be higher than edge capacities. Our algorithm for this case improves the best known approximation ratio. We also give a lower bound that shows that the extended UFP is provably harder than the classical UFP. Finally, we consider the bounded UFP in which the maximum demand is at most 1/K times the minimum edge capacity for some K > 1. Here we provide combinatorial algorithms that match the currently best known algorithms. All of our algorithms are strongly polynomial and some can even be used in the online setting.     

Actor-critic algorithms for hierarchical Markov decision processes

We consider the problem of control of hierarchical Markov decision processes and develop a simulation based two-timescale actor-critic algorithm in a general framework. We also develop certain approximation algorithms that require less computation and satisfy a performance bound. One of the approximation algorithms is a three-timescale actor-critic algorithm while the other is a two-timescale algorithm, however, which operates in two separate stages. All our algorithms recursively update randomized policies using the simultaneous perturbation stochastic approximation (SPSA) methodology. We briefly present the convergence analysis of our algorithms. We then present numerical experiments on a problem of production planning in semiconductor fabs on which we compare the performance of all algorithms together with policy iteration. Algorithms based on certain Hadamard matrix based deterministic perturbations are found to show the best results.     

Dicing on the Streett

Streett/Rabin games are an adequate model of strong fairness in reactive systems. We show here some results about their stochastic version. We extend the known lower bound in memory for the pure winning strategies of the Streett player to randomized strategies. We also propose algorithms computing the almost sure winning regions of both players in stochastic Streett/Rabin games. The Rabin algorithm also yields directly a pure memoryless almost-sure winning strategy.     

A randomized sublinear time parallel GCD algorithm for the EREW PRAM

We present a randomized parallel algorithm that computes the greatest common divisor of two integers of n bits in length with probability 1−o(1) that takes O(nloglogn/logn) time using O(n6+?) processors for any ?>0 on the EREW PRAM parallel model of computation. The algorithm either gives a correct answer or reports failure.We believe this to be the first randomized sublinear time algorithm on the EREW PRAM for this problem.     

Horizon computation on a hierarchical triangulated terrain model

Hierarchical terrain models describe a topographic surface at different levels of detail, thus providing a multiresolution surface representation as well as a data compression mechanism. We consider the horizon computation problem on a hierarchical polyhedral terrain (in particular, on a hierarchical triangulated irregular network), which involves extracting the horizon of a viewpoint at a given resolution and updating it as the resolution increases. We present an overview of horizon computation algorithms on a nonhierarchical polyhedral terrain. We extend such algorithms to the hierarchical case by describing a method which extracts the terrain edges at a given resolution, and proposing a randomized algorithm for dynamically updating a horizon under insertions and deletions of terain edges     

Offline file assignments for online load balancing

We study a novel load balancing problem that arises in web search engines. The problem is a combination of an offline assignment problem, where files need to be (copied and) assigned to machines, and an online load balancing problem, where requests ask for specific files and need to be assigned to a corresponding machine, whose load is increased by this.We present simple deterministic algorithms for this problem and exhibit an interesting trade-off between the available space to make file copies and the obtainable makespan. We also give non-trivial lower bounds for a large class of deterministic algorithms and present a randomized algorithm that beats these bounds with high probability.     

The inherent price of indulgence

An indulgent algorithm is a distributed algorithm that tolerates asynchronous periods of the network when process crash detection is unreliable. This paper presents a tight bound on the time complexity of indulgent consensus algorithms. We consider a round-based eventually synchronous model, and we show that any t-resilient consensus algorithm in this model, requires at least t+2 rounds for a global decision even in runs that are synchronous. We contrast our lower bound with the well-known t+1 round tight bound on consensus in the synchronous model. We then prove the bound to be tight by exhibiting a new t-resilient consensus algorithm in the eventually synchronous model that reaches a global decision at round t+2 in every synchronous run. Our new algorithm is in this sense significantly faster than the most efficient indulgent algorithm we know of, which requires 2t+2 rounds in synchronous runs. Our lower bound applies to round-based consensus algorithms with unreliable failure detectors such as ⋄ P and ⋄ S, and our matching algorithm can be adapted to such failure detectors. This work is partially supported by the Swiss National Science Foundation (project number 510-207).     

Towards hybrid evolutionary algorithms

Metaheuristics have received considerable interest these recent years in the field of combinatorial optimization. However, the choice of a particular algorithm to optimize a certain problem is still mainly driven by some sort of devotion of its author to a certain technique rather than by a rationalistic choice driven by reason. Hybrid algorithms have shown their ability to provide local optima of high quality. Hybridization of algorithms is still in its infancy: certain combinations of algorithms have experimentally shown their performance, though the reasons of their success is not always really clear. In order to add some rational to these issues, we study the structure of search spaces and attempt to relate it to the performance of algorithms. We wish to explain the behavior of search algorithms with this knowledge and provide guidelines in the design of hybrid algorithms. This paper briefly reviews the current knowledge we have on search spaces of combinatorial optimization problems. Then, we discuss hybridization and present a general classification of the way hybridization can be conducted in the light of our knowledge of the structure of search spaces.     

Quasi-Fully Dynamic Algorithms for Two-Connectivity and Cycle Equivalence

We introduce a new class of dynamic graph algorithms called quasi-fully dynamic algorithms , which are much more general than backtracking algorithms and are much simpler than fully dynamic algorithms. These algorithms are especially suitable for applications in which a certain core connected portion of the graph remains fixed, and fully dynamic updates occur on the remaining edges in the graph. We present very simple quasi-fully dynamic algorithms with O(log n) worst-case time per operation for 2-edge connectivity and O(log n) amortized time per operation for cycle equivalence. The former is deterministic while the latter is Monte-Carlo-type randomized. For 2-vertex connectivity, we give a deterministic quasi-fully dynamic algorithm with O(log ³ n) amortized time per operation. The quasi-fully dynamic algorithm we present for cycle equivalence (which has several applications in optimizing compilers) is of special interest since the algorithm is quite simple, and no special-purpose incremental or backtracking algorithm is known for this problem. Received October 26, 1998; revised October 1, 1999, and April 15, 2001.     

On the Influence of Lookahead in Competitive Paging Algorithms

We introduce a new model of lookahead for on-line paging algorithms and study several algorithms using this model. A paging algorithm is n-line with strong lookahead l if it sees the present request and a sequence of future requests that contains l pairwise distinct pages. We show that strong lookahead has practical as well as theoretical importance and improves the competitive factors of on-line paging algorithms. This is the first model of lookahead having such properties. In addition to lower bounds we present a number of deterministic and randomized on-line paging algorithms with strong lookahead which are optimal or nearly optimal. Received April 8, 1994; revised May 15, 1995.     

Models of Greedy Algorithms for Graph Problems

Borodin et al. (Algorithmica 37(4):295–326, 2003) gave a model of greedy-like algorithms for scheduling problems and Angelopoulos and Borodin (Algorithmica 40(4):271–291, 2004) extended their work to facility location and set cover problems. We generalize their model to include other optimization problems, and apply the generalized framework to graph problems. Our goal is to define an abstract model that captures the intrinsic power and limitations of greedy algorithms for various graph optimization problems, as Borodin et al. (Algorithmica 37(4):295–326, 2003) did for scheduling. We prove bounds on the approximation ratio achievable by such algorithms for basic graph problems such as shortest path, weighted vertex cover, Steiner tree, and independent set. For example, we show that, for the shortest path problem, no algorithm in the FIXED priority model can achieve any approximation ratio (even one dependent on the graph size), but the well-known Dijkstra’s algorithm is an optimal ADAPTIVE priority algorithm. We also prove that the approximation ratio for weighted vertex cover achievable by ADAPTIVE priority algorithms is exactly 2. Here, a new lower bound matches the known upper bounds (Johnson in J. Comput. Syst. Sci. 9(3):256–278, 1974). We give a number of other lower bounds for priority algorithms, as well as a new approximation algorithm for minimum Steiner tree problem with weights in the interval [1,2]. S. Davis’ research supported by NSF grants CCR-0098197, CCR-0313241, and CCR-0515332. Views expressed are not endorsed by the NSF. R. Impagliazzo’s research supported by NSF grant CCR-0098197, CCR-0313241, and CCR-0515332. Views expressed are not endorsed by the NSF. Some work done while at the Institute for Advanced Study, supported by the State of New Jersey.     

How efficiently can room at the bottom be traded away for speed at the top?

Given exponential 2 ⁿ space, we know that an Adleman-Lipton computation can decide many hard problems – such as boolean formula and boolean circuit evaluation – in a number of steps that is linear in the problem size n. We wish to better understand the process of designing and comparing bio-molecular algorithms that trade away weakly exponential space to achieve as low a running time as possible, and to analyze the efficiency of their space and time utilization relative to those of their best extant classical/bio-molecular counterparts. We propose a randomized framework which augments that of the sticker model of Roweis et al. to provide an abstract setting for analyzing the space-time efficiency of both deterministic and randomized bio-molecular algorithms. We explore its power by developing and analyzing such algorithms for theCovering Code Creation (CCC) and k-SAT problems. In the process, we uncover new classical algorithms for CCC andk-SAT that, while exploiting the same space-time trade-off as the best previously known classical algorithms, are exponentially more efficient than them in terms of space-time product utilization. This work indicates that the proposed abstract bio-molecular setting for randomized algorithm design provides a logical tool of independent interest. This revised version was published online in June 2006 with corrections to the Cover Date.     

Randomized algorithms for quadratic stability of quantized sampled-data systems

In this paper, we present a novel development of randomized algorithms for quadratic stability analysis of sampled-data systems with memoryless quantizers. The specific randomized algorithm employed generates a quadratic Lyapunov function and leads to realistic bounds on the performance of such systems. A key feature of this method is that the characteristics of quantizers are exploited to make the algorithm computationally efficient.     

On the power of randomization in on-line algorithms

Against in adaptive adversary, we show that the power of randomization in on-line algorithms is severely limited! We prove the existence of an efficient simulation of randomized on-line algorithms by deterministic ones, which is best possible in general. The proof of the upper bound is existential. We deal with the issue of computing the efficient deterministic algorithm, and show that this is possible in very general cases.A previous version of this paper appeared in the22nd ACM STOC Conference Proceedings. Part of this research was performed while A. Borodin and A. Wigderson were visitors at the International Computer Science Institute, and while G. Tardos was a visitor at the Hebrew University.     

Feedback arc set problem in bipartite tournaments

In this paper we give ratio 4 deterministic and randomized approximation algorithms for the Feedback Arc Set problem in bipartite tournaments. We also generalize these results to give a factor 4 deterministic approximation algorithm for Feedback Arc Set problem in multipartite tournaments.     

Leveraging saving-based algorithms by master-slave genetic algorithms

Saving-based algorithms are commonly used as inner mechanisms of efficient heuristic construction procedures. We present a general mechanism for enhancing the effectiveness of such heuristics based on a two-level genetic algorithm. The higher-level algorithm searches in the space of possible merge lists which are then used by the lower-level saving-based algorithm to build the solution. We describe the general framework and we illustrate its application to three hard combinatorial problems. Experimental results on three hard combinatorial optimization problems show that the approach is very effective and it enables considerable enhancement of the performance of saving-based algorithms.     

The SR-GCWS hybrid algorithm for solving the capacitated vehicle routing problem

The capacitated vehicle routing problem (CVRP) is a well known problem which has long been tackled by researchers for several decades now, not only because of its potential applications but also due to the fact that CVRP can be used to test the efficiency of new algorithms and optimization methods. The objective of our work is to present SR-GCWS, a hybrid algorithm that combines a CVRP classical heuristic with Monte Carlo simulation using state-of-the-art random number generators. The resulting algorithm is tested against some well-known benchmarks. In most cases, our approach is able to compete or even outperform much more complex algorithms, which is especially interesting if we consider that our algorithm does not require any previous parameter fine-tuning or set-up process. Moreover, our algorithm has been able to produce high-quality solutions almost in real-time for most tested instances. Another important feature of the algorithm worth mentioning is that it uses a randomized constructive heuristic, capable of generating hundreds or even thousands of alternative solutions with different properties. These alternative solutions, in turn, can be really useful for decision-makers in order to satisfy their utility functions, which are usually unknown by the modeler. The presented methodology may be a fine framework for the development of similar algorithms for other complex combinatorial problems in the routing arena as well as in some other research fields.