Incremental facility location problem and its competitive algorithms

DOI10.1007/s10878-009-9219-8zbMath1205.90242OpenAlexW2032152618MaRDI QIDQ604759

Wenqiang Dai, Xianju Zeng

Publication date: 12 November 2010

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-009-9219-8

zbMATH Keywords

competitive ratioonline algorithmanalysis of algorithm

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items (3)

A 16-competitive algorithm for hierarchical median problem ⋮ Unnamed Item ⋮ Online economic ordering problem for deteriorating items with limited price information

Cites Work

• Searching in an unknown environment: An optimal randomized algorithm for the cow-path problem
• An improved approximation ratio for the minimum latency problem
• A new approximation algorithm for the \(k\)-facility location problem
• Incremental medians via online bidding
• 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
• A new greedy approach for facility location problems
• Greedy Strikes Back: Improved Facility Location Algorithms
• The Online Median Problem
• Local search heuristic for k-median and facility location problems
• Profit-earning facility location
• Better Bounds for Incremental Medians
• An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Incremental facility location problem and its competitive algorithms