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...
详细信息
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].
We present a series of results regarding conceptually simple algorithms for bipartite matching in various online and related models. We first consider a deterministic adversarial model. The best approximation ratio in...
详细信息
We present a series of results regarding conceptually simple algorithms for bipartite matching in various online and related models. We first consider a deterministic adversarial model. The best approximation ratio in this model is 1/2, which is achieved by any greedy algorithm. Durr et al. (2016) presented a 2-pass algorithm Category-Advice with approximation ratio 3/5. We extend their algorithm to multiple passes. We prove the exact approximation ratio for the k-pass Category-Advice algorithm for all k >= 1, and show that the approximation ratio converges quickly to the inverse of the golden ratio 2/(1+5)approximate to 0.618\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$2/(1+\sqrt {5}) \approx 0.618$\end{document} as k goes to infinity. We then consider a natural adaptation of a well-known offline MinGreedy algorithm to the online stochastic IID model, which we call MinDegree. In spite of excellent empirical performance of MinGreedy, it was recently shown to have approximation ratio 1/2 in the adversarial offline setting - the approximation ratio achieved by any greedy algorithm. Our result in the online known IID model is, in spirit, similar to the offline result, but the proof is different. We show that MinDegree cannot achieve an approximation ratio better than 1 - 1/e, which is guaranteed by any consistent greedy algorithm in the known IID model. Finally, following the work in Besser and Poloczek (Algorithmica 2017(1), 201-234, 2017), we depart from an adversarial or stochastic ordering and investigate a natural randomized algorithm (MinRanking) in the priority model. Although the priority model allows the algorithm to choose the input ordering in a general but well defined way, this natural algorithm cannot obtain the approximation of the Ranking algorithm in the ROM model.
The surprising results of Karp, Vazirani and Vazirani [39] and (respectively) Buchbinder et al. [18] are examples where rather simple randomization provides provably better approximations than the corresponding determ...
详细信息
The surprising results of Karp, Vazirani and Vazirani [39] and (respectively) Buchbinder et al. [18] are examples where rather simple randomization provides provably better approximations than the corresponding deterministic counterparts for online bipartite matching and (respectively) unconstrained non-monotone submodular. We show that seemingly strong extensions of the deterministic online computation model can at best match the performance of naive randomization. More specifically, for bipartite matching, we show that in the priority model (allowing very general ways to order the input stream), we cannot improve upon the trivial approximation achieved by any greedy maximal matching algorithm and likewise cannot improve upon this approximation by logn/lonlogn number of online algorithms running in parallel. The latter result yields an improved log logn - logloglogn lower bound for the number of advice bits needed to beat the simple deterministic greedy algorithm. For max-sat, we adapt the recent de-randomization approach of Buchbinder and Feldman [16] applied to the Buchbinder et al. [17] algorithm for max-sat to obtain a deterministic 3/4 approximation algorithm using width 2n parallelism. In order to improve upon this approximation, we show that exponential width parallelism of online algorithms is necessary (in a model that is more general than what is needed for the width 2n algorithm). We relate our results to previous work concerning the priority Branching Tree (pBT) model of Alekhnovich et al. [2]. (C) 2018 Elsevier B.V. All rights reserved.
We define a formal model of dynamic programming algorithms which we call Prioritized Branching Programs (pBP). Our model is a generalization of the BT model of Alekhnovich et al. (IEEE Conference on Computational Comp...
详细信息
We define a formal model of dynamic programming algorithms which we call Prioritized Branching Programs (pBP). Our model is a generalization of the BT model of Alekhnovich et al. (IEEE Conference on Computational Complexity, pp. 308-322, 2005), which is in turn a generalization of the priority algorithms model of Borodin, Nielson and Rackoff. One of the distinguishing features of these models is that they not only capture large classes of algorithms generally considered to be greedy, backtracking or dynamic programming algorithms, but they also allow characterizations of their limitations. Hence they give meaning to the statement that a given problem can or cannot be solved by dynamic programming. After defining the model, we prove three main results: (i) that certain types of natural restrictions of our seemingly more powerful model can be simulated by the BT model;(ii) that in general our model is stronger than the BT model-a fact which is witnessed by the classical shortest paths problem;(iii) that our model has very real limitations, namely that bipartite matching cannot be efficiently computed in it, hence suggesting that there are problems that can be solved efficiently by network flow algorithms and by simple linear programming that cannot be solved by natural dynamic programming approaches.
Borodin, Nielsen and Rackoff [5] proposed a framework for abstracting the main properties of greedy-like algorithms with emphasis on scheduling problems, and Davis and Impagliazzo [6] extended it so as to make it appl...
详细信息
ISBN:
(纸本)354024574X
Borodin, Nielsen and Rackoff [5] proposed a framework for abstracting the main properties of greedy-like algorithms with emphasis on scheduling problems, and Davis and Impagliazzo [6] extended it so as to make it applicable to graph optimization problems. In this paper we propose a related model which places certain reasonable restrictions on the power of the greedy-like algorithm. Our goal is to define a model in which it is possible to filter out certain overly powerful algorithms, while still capturing a very rich class of greedy-like algorithms. We argue that this approach better motivates the lower-bound proofs and possibly yields better bounds. To illustrate the techniques involved we apply the model to the well-known problems of (complete) facility location and dominating set.
Real-time systems are used in a wide range of applications, including control, sensing, multimedia, etc. Scheduling is a central problem for these computing/communication systems since responsible of software ex...
详细信息
ISBN:
(数字)9781118984406
ISBN:
(纸本)9781848216655
Real-time systems are used in a wide range of applications, including control, sensing, multimedia, etc. Scheduling is a central problem for these computing/communication systems since responsible of software execution in a timely manner. This book provides state of knowledge in this domain with special emphasis on the key results obtained within the last decade. This book addresses foundations as well as the latest advances and findings in Real-Time Scheduling, giving all references to important papers. But nevertheless the chapters will be short and not overloaded with confusing details. Coverage includes scheduling approaches for mono-core as well as multi-core platforms, dependent tasks, networks, and notably very tremendous recent advances in scheduling of energy constrained embedded systems. Other sophisticated issues such as feedback control scheduling and timing analysis of critical applications are also addressed. This volume can serve as a textbook for courses on the topic in bachelor and in more advanced master programs. It also provides a reference for computer scientists and engineers involved in the design or the development of Cyber-Physical Systems which require up-to-date real-time scheduling solutions.
暂无评论