Incremental medians via online bidding

DOI10.1007/S00453-007-9005-XzbMath1216.90057OpenAlexW2167112911MaRDI QIDQ2482726

Marek Chrobak, John Noga, 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

Analysis of algorithms (68W40) Discrete location and assignment (90B80) Auctions, bargaining, bidding and selling, and other market models (91B26) Randomized algorithms (68W20)

Related Items (17)

Optimal search for parameters in Monte Carlo simulation for derivative pricing ⋮ Incremental facility location problem and its competitive algorithms ⋮ Competitive Strategies for Online Clique Clustering ⋮ An incremental version of the \(k\)-center problem on boundary of a convex polygon ⋮ A 16-competitive algorithm for hierarchical median problem ⋮ Online multiple-strip packing ⋮ Online minimization knapsack problem ⋮ Improved bounds for randomized preemptive online matching ⋮ The inverse 1-median problem on tree networks with variable real edge lengths ⋮ An approximation algorithm for the Euclidean incremental median problem ⋮ New results on multi-level aggregation ⋮ Optimal online-list batch scheduling ⋮ Online clique clustering ⋮ Clairvoyant Mechanisms for Online Auctions ⋮ Randomized algorithms for online bounded bidding ⋮ Unnamed Item ⋮ General bounds for incremental maximization

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

This page was built for publication: Incremental medians via online bidding