Improved complexity bounds for location problems on the real line

DOI10.1016/0167-6377(91)90041-MzbMath0742.90050OpenAlexW2044016543MaRDI QIDQ1180820

Publication date: 27 June 1992

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0167-6377(91)90041-m

zbMATH Keywords

complexity bounds median problems coverage location models on the real line

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Continuous location (90B85) Sensitivity, stability, parametric optimization (90C31) Dynamic programming (90C39) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items (43)

Using geometric techniques to improve dynamic programming algorithms for the economic lot-sizing problem and extensions ⋮ Strongly polynomial efficient approximation scheme for segmentation ⋮ Efficient algorithms for centers and medians in interval and circular-arc graphs ⋮ Capacitated Arc Stabbing ⋮ Location and sizing of facilities on a line ⋮ The general facility location problem with connectivity on trees ⋮ Representation of the non-dominated set in biobjective discrete optimization ⋮ A global shooting algorithm for the facility location and capacity acquisition problem on a line with dense demand ⋮ The directional \(p\)-median problem: definition, complexity, and algorithms ⋮ Revisiting \(k\)-sum optimization ⋮ Structured \(p\)-facility location problems on the line solvable in polynomial time ⋮ Partial multicovering and the \(d\)-consecutive ones property ⋮ Improved algorithms for path partition and related problems ⋮ The Coverage Problem by Aligned Disks ⋮ The coverage problem by aligned disks ⋮ Locating an axis-parallel rectangle on a Manhattan plane ⋮ Minimum \(L_k\) path partitioning-an illustration of the Monge property ⋮ Line-Constrained k-Median, k-Means, and k-Center Problems in the Plane ⋮ Optimal Control Strategies for Incoming Inspection ⋮ An Improved Competitive Algorithm for One-Dimensional Incremental Median Problem ⋮ Locating public facilities by majority: stability, consistency and group formation ⋮ New algorithms for facility location problems on the real line ⋮ The \(k\)-centrum multi-facility location problem ⋮ Online facility location with facility movements ⋮ On the p‐coverage problem on the real line ⋮ Information Loss in Grade Point Conversion ⋮ Capacitated location-allocation problems on a line ⋮ Minsum \(k\)-sink problem on path networks ⋮ On the parameterized complexity of multiple-interval graph problems ⋮ A polynomial method for the pos/neg weighted 3-median problem on a tree ⋮ On some efficiently solvable classes of the network facility location problem with constraints on the capacities of communication lines ⋮ GEOMETRIC ALGORITHMS FOR THE CONSTRAINED 1-D K-MEANS CLUSTERING PROBLEMS AND IMRT APPLICATIONS ⋮ Scheduling with gaps: new models and algorithms ⋮ Improved algorithms for the multicut and multiflow problems in rooted trees ⋮ Approximating Distance Measures for the Skyline ⋮ Aggregation error for location models: Survey and analysis ⋮ Improved complexity results for several multifacility location problems on trees ⋮ Optimal algorithms for selective variants of the classical and inverse median location problems on trees ⋮ Multicuts and integral multiflows in rings ⋮ An \(O(pn^ 2)\) algorithm for the \(p\)-median and related problems on tree graphs ⋮ 2-medians in trees with pos/neg weights ⋮ The least element property of center location on tree networks with applications to distance and precedence constrained problems ⋮ Locating stops along bus or railway lines -- a bicriteria problem

Cites Work

This page was built for publication: Improved complexity bounds for location problems on the real line