Randomized priority algorithms

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

zbMATH Keywords

facility locationgreedy algorithmsrandomized approximation algorithmsmakespan scheduling

Mathematics Subject Classification ID

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