An approximate cost recovery scheme for the k-product facility location game with penalties

DOI10.1016/J.TCS.2024.114933MaRDI QIDQ6639743zbMATH OpenFDO

Authors Xiaowei Li, Xiwen Lu

Publication date 18 November 2024

Published in Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

facility location gamecompetitiveapproximate cost recoverycross-monotoniccost-sharing scheme

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Applications of game theory (91A80) Discrete location and assignment (90B80)

Recommendations

• A cost-sharing scheme for the \(k\)-level facility location game with penalties
• A cost-sharing method for an uncapacitated facility location game with penalties
• The \(k\)-level facility location game
• A cross-monotonic cost-sharing scheme for the concave facility location game
• A cross-monotonic cost sharing method for the facility location game with service installation costs

Cites work

• scientific article; zbMATH DE number 1559542 (Why is no real title available?)
• A 1.488 approximation algorithm for the uncapacitated facility location problem
• A 3-approximation algorithm for the \(k\)-level uncapacitated facility location problem
• A \(k\)-product uncapacitated facility location problem
• A combinatorial approximation algorithm for \(k\)-level facility location problem with submodular penalties
• A cost-sharing method for an uncapacitated facility location game with penalties
• A cost-sharing scheme for the \(k\)-level facility location game with penalties
• A note on LP-based approximation algorithms for capacitated facility location problem
• Algorithms for facility location problems with outliers. (Extended abstract)
• An LP-rounding based algorithm for a capacitated uniform facility location problem with penalties
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Greedy Strikes Back: Improved Facility Location Algorithms
• Improved Approximation Algorithms for the Uncapacitated Facility Location Problem
• LP-based algorithms for capacitated facility location
• LP-based approximation for uniform capacitated facility location problem
• Limitations of cross-monotonic cost-sharing schemes
• Strategyproof sharing of submodular costs: budget balance versus efficiency
• The \(k\)-level facility location game
• The design of approximation algorithms

This page was built for publication: An approximate cost recovery scheme for the \(k\)-product facility location game with penalties

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