A nearly optimal deterministic online algorithm for non-metric facility location

DOI10.4230/LIPICS.STACS.2021.14MaRDI QIDQ7231537zbMATH OpenFDO

Authors Marcin Bienkowski, Björn Feldkord, Paweł Schmidt

Publication date 21 April 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.STACS.2021.14

zbMATH Keywords

deterministic roundingfacility locationlinear programmingonline algorithmsset cover

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A 1.488 approximation algorithm for the uncapacitated facility location problem
• A general approach to online network optimization problems
• A new greedy approach for facility location problems
• A primal-dual algorithm for online non-uniform facility location
• A simple and deterministic competitive algorithm for online facility location
• A threshold of ln n for approximating set cover
• An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem
• Analysis of a Local Search Heuristic for Facility Location Problems
• Approximation Algorithms for Metric Facility Location Problems
• Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
• Heuristics for the fixed cost median problem
• scientific article; zbMATH DE number 1670526 (Why is no real title available?)
• scientific article; zbMATH DE number 9246 (Why is no real title available?)
• scientific article; zbMATH DE number 1559542 (Why is no real title available?)
• scientific article; zbMATH DE number 910872 (Why is no real title available?)
• Improved Approximation Algorithms for the Uncapacitated Facility Location Problem
• Improved Combinatorial Algorithms for Facility Location Problems
• Near-optimal online algorithms for prize-collecting Steiner problems
• On the competitive ratio for online facility location
• Online Node-weighted Steiner Forest and Extensions via Disk Paintings
• Online node-weighted Steiner tree and related problems
• Online primal-dual algorithms for covering and packing
• Probabilistic construction of deterministic algorithms: approximating packing integer programs
• The Design of Competitive Online Algorithms via a Primal—Dual Approach
• The multiplicative weights update method: a meta-algorithm and applications
• The online set cover problem

Cited in

(1)

• Online disjoint set covers: randomization is not necessary

This page was built for publication: A nearly optimal deterministic online algorithm for non-metric facility location

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7231537)