Randomized priority algorithms
From MaRDI portal
Publication:974749
DOI10.1016/j.tcs.2010.03.014zbMath1203.68312OpenAlexW2120954276MaRDI QIDQ974749
Spyros Angelopoulos, Allan Borodin
Publication date: 7 June 2010
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2010.03.014
Deterministic scheduling theory in operations research (90B35) Discrete location and assignment (90B80) Approximation algorithms (68W25) Randomized algorithms (68W20)
Related Items (5)
Erratum to: ``Greedy matching: guarantees and limitations ⋮ On extensions of the deterministic online model for bipartite matching and max-sat ⋮ Greedy matching: guarantees and limitations ⋮ On conceptually simple algorithms for variants of online bipartite matching ⋮ Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A lower bound for randomized on-line multiprocessor scheduling
- A better lower bound on the competitive ratio of the randomized 2-server problem
- Toward a model for backtracking and dynamic programming
- Hierarchies for classes of priority algorithms for job scheduling
- New algorithms for an ancient scheduling problem.
- Bubblesearch: a simple heuristic for improving priority-based greedy algorithms
- Online algorithms. The state of the art
- On the power of randomization in on-line algorithms
- A lower bound for randomized on-line scheduling algorithms
- (Incremental) priority algorithms
- Priority algorithms for makespan minimization in the subset model.
- The power of priority algorithms for facility location and set cover
- On the competitive ratio for online facility location
- Approximating the Throughput of Multiple Machines in Real-Time Scheduling
- Note on Independence Functions
- Crossing Number is NP-Complete
- Greedoids and Linear Objective Functions
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- A new greedy approach for facility location problems
- On randomized online scheduling
- Priority Algorithms for the Subset-Sum Problem
- On the Greedy Solution of Ordering Problems
- Algorithms for Scheduling Independent Tasks
- Greedy Strikes Back: Improved Facility Location Algorithms
- An optimal on-line algorithm for metrical task system
- Generating Sparse 2-Spanners
- Interval selection: Applications, algorithms, and lower bounds
- The Online Median Problem
- Bounds for Certain Multiprocessing Anomalies
- Bounds on Multiprocessing Timing Anomalies
- Matroids and the greedy algorithm
- Approximation and Online Algorithms
- Automata, Languages and Programming
- Approximation and Online Algorithms
- Semi-online scheduling with decreasing job sizes
This page was built for publication: Randomized priority algorithms
