Randomized priority algorithms

DOI10.1016/j.tcs.2010.03.014zbMath1203.68312MaRDI QIDQ974749

Allan Borodin, Spyros Angelopoulos

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 location; greedy algorithms; randomized approximation algorithms; makespan scheduling

Mathematics Subject Classification ID

90B35: Deterministic scheduling theory in operations research

90B80: Discrete location and assignment

68W25: Approximation algorithms

68W20: Randomized algorithms

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