Facility location problems: a parameterized view

DOI10.1016/j.dam.2011.03.021zbMath1218.90100OpenAlexW2080239175WikidataQ57359683 ScholiaQ57359683MaRDI QIDQ2275913

Michael R. Fellows, Henning Fernau

Publication date: 10 August 2011

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2011.03.021

zbMATH Keywords

NP-completenessparameterized algorithmsexact algorithmsfacility location problemssemistructured documents

Mathematics Subject Classification ID

Applications of mathematical programming (90C90) Abstract computational complexity for mathematical programming problems (90C60) Discrete location and assignment (90B80)

Related Items (7)

On the Parameterized Complexity of the Expected Coverage Problem ⋮ On the parameterized complexity of the expected coverage problem ⋮ Finding a collective set of items: from proportional multirepresentation to group recommendation ⋮ Polynomial-time data reduction for weighted problems beyond additive goal functions ⋮ Partition on trees with supply and demand: kernelization and algorithms ⋮ A multi-parameter analysis of hard problems on deterministic finite automata ⋮ Representative families for matroid intersections, with applications to location, packing, and covering problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On problems without polynomial kernels
• Some simplified NP-complete graph problems
• Complexity-based induction
• A constant-factor approximation algorithm for the \(k\)-median problem
• The Turing way to parameterized complexity
• Capacitated Domination and Covering: A Parameterized Perspective
• Facility Location Problems: A Parameterized View
• Fourier meets M\"{o}bius: fast subset convolution
• Incompressibility through Colors and IDs
• Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
• Kernel Bounds for Disjoint Cycles and Disjoint Paths
• Capacitated vertex covering
• Convergence of the Lloyd Algorithm for Computing Centroidal Voronoi Tessellations
• Grammatical Inference: Algorithms and Applications
• An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem

This page was built for publication: Facility location problems: a parameterized view