Worst-Case and Probabilistic Analysis of a Geometric Location Problem

DOI10.1137/0210040zbMath0461.68078OpenAlexW2079886069MaRDI QIDQ3911420

Christos H. Papadimitriou

Publication date: 1981

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0210040

zbMATH Keywords

NP-completeprobabilistic analysis of algorithmsK-median problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99)

Related Items (36)

The searching over separators strategy to solve some NP-hard problems in subexponential time ⋮ Aggregation in hub location problems ⋮ A theory for memory-based learning ⋮ Geometric optimization and the polynomial hierarchy ⋮ Maximal paths in random dynamic graphs ⋮ A note on duality gap in the simple plant location problem ⋮ Combinational optimization problems for which almost every algorithm is asymptotically optimal ⋮ Cluster analysis from molecular similarity matrices using a nonlinear neural network ⋮ Computational complexity of the problem of choosing typical representatives in a 2-clustering of a finite set of points in a metric space ⋮ Solving large \(p\)-median problems by a multistage hybrid approach using demand points aggregation and variable neighbourhood search ⋮ A double annealing algorithm for discrete location/allocation problems ⋮ Discrete facility location in machine learning ⋮ Recovery guarantees for exemplar-based clustering ⋮ An Approximation Algorithm for the Continuous k-Medians Problem in a Convex Polygon ⋮ Quantum speed-up for unsupervised learning ⋮ A space-indexed formulation of packing boxes into a larger box ⋮ Complexity of some problems of quadratic partitioning of a finite set of points in Euclidean space into balanced clusters ⋮ Wasserstein Distance and the Distributionally Robust TSP ⋮ Exploiting Packing Components in General-Purpose Integer Programming Solvers ⋮ Dynamic and static algorithms for optimal placement of resources in a tree ⋮ Unnamed Item ⋮ Placing resources in a tree: Dynamic and static algorithms ⋮ Worst-case demand distributions in vehicle routing ⋮ Competitive location in the plane ⋮ On solving unreliable planar location problems ⋮ Max-Min Problems of Searching for Two Disjoint Subsets ⋮ NP-completeness of some problems of partitioning a finite set of points in Euclidean space into balanced clusters ⋮ Heuristic methods and applications: A categorized survey ⋮ On the k-center problem with many centers ⋮ Worst-case analysis of demand point aggregation for the Euclidean \(p\)-median problem ⋮ On the complexity of locating linear facilities in the plane ⋮ 2-medians in trees with pos/neg weights ⋮ A Probabilistic Analysis of the K-Location Problem ⋮ Models for planning capacity expansion in local access telecommunication networks ⋮ Probabilistic Analysis of Geometric Location Problems ⋮ Probabilistic analysis of two \(k\)-cluster problems

This page was built for publication: Worst-Case and Probabilistic Analysis of a Geometric Location Problem