Incremental medians via online bidding

DOI10.1007/s00453-007-9005-xzbMath1216.90057MaRDI QIDQ2482726

John Noga, Marek Chrobak, Neal E. Young, Claire M. Kenyon

Publication date: 23 April 2008

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-007-9005-x

Mathematics Subject Classification ID

68W40: Analysis of algorithms

90B80: Discrete location and assignment

91B26: Auctions, bargaining, bidding and selling, and other market models

68W20: Randomized algorithms

Related Items

Incremental facility location problem and its competitive algorithms, Online multiple-strip packing, Randomized algorithms for online bounded bidding, Optimal online-list batch scheduling

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Searching in an unknown environment: An optimal randomized algorithm for the cow-path problem
• The reverse greedy algorithm for the metric k-median problem
• Approximation algorithms for geometric median problems
• An improved approximation ratio for the minimum latency problem
• Nonclairvoyant scheduling
• Performance guarantees for hierarchical clustering
• A constant-factor approximation algorithm for the \(k\)-median problem
• Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Oblivious Medians Via Online Bidding
• A new greedy approach for facility location problems
• Multi-processor scheduling to minimize flow time with ε resource augmentation
• A general approach for incremental approximation and hierarchical clustering
• Speed is as powerful as clairvoyance
• Analysis of a Local Search Heuristic for Facility Location Problems
• Local Search Heuristics for k-Median and Facility Location Problems
• The Online Median Problem
• Local search heuristic for k-median and facility location problems
• Improved Combinatorial Algorithms for Facility Location Problems
• Algorithms - ESA 2003