The algebraic degree of geometric optimization problems

DOI10.1007/BF02187906zbMath0647.90087OpenAlexW2071857538WikidataQ29307364 ScholiaQ29307364MaRDI QIDQ1104865

Publication date: 1988

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/186386

zbMATH Keywords

facility location algebraic degree classic Weber problem Galois methods line-restricted Weber problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonlinear programming (90C30) Inventory, storage, reservoirs (90B05) Mathematical programming (90C99)

Related Items

Medians in median graphs and their cube complexes in linear time, On stars and Steiner stars, A geometric characterisation of the quadratic min-power centre, The algebraic degree of semidefinite programming, Largest and smallest convex hulls for imprecise points, How bad can the centroid be?, Finding a Hausdorff Core of a Polygon: On Convex Polygon Containment with Bounded Hausdorff Distance, Geometric optimization and \(D^ P\)-completeness, Computing the Rectilinear Center of Uncertain Points in the Plane, An approximation algorithm for computing shortest paths in weighted 3-d domains, Improved upper bounds for the Steiner ratio, Robustness and asymptotics of the projection median, The Fermat-Torricelli problem. I: A discrete gradient-method approach, Optimal gathering of oblivious robots in anonymous graphs and its application on trees and rings, The Fermat-Torricelli theorem in convex geometry, Gathering of robots on meeting-points: feasibility and optimal resolution algorithms, Simple approximative algorithms for free-support Wasserstein barycenters, Similarity of polygonal curves in the presence of outliers, On triangulation axes of polygons, On the probabilistic behaviour of a heuristic algorithm for maximal Hamiltonian tours, Skeletal configurations of ribbon trees, Minimal NMR distance information for rigidity of protein graphs, On Combinatorial Depth Measures, The projection median of a set of points in \({\mathbb{R}}^{d}\), Leader election and gathering for asynchronous fat robots without common chirality, Improved PTASs for convex barrier coverage, One-dimensional \(k\)-center on uncertain data, A nearly optimal algorithm to decompose binary forms, A note on the unsolvability of the weighted region shortest path problem, Gathering of oblivious robots on infinite grids with minimum traveled distance, Generalized median graph computation by means of graph embedding in vector spaces, SMOOTHING IMPRECISE 1.5D TERRAINS, Improved bounds on the average distance to the Fermat-Weber center of a convex object, Facility location problems with uncertainty on the plane, Speeding up dynamic programming in the line-constrained \(k\)-median, Speeding up Dynamic Programming in the Line-Constrained k-median, The projection median of a set of points, Single facility collection depots location problem in the plane, Power-aware scheduling for makespan and flow, On the Fermat-Weber center of a convex object, The Weiszfeld Algorithm: Proof, Amendments, and Extensions, A quantum approach to the discretizable molecular distance geometry problem, The dynamics and internal geometry of the three-city noxious location problem, On minimum- and maximum-weight minimum spanning trees with neighborhoods, The Fermat-Torricelli point and isosceles tetrahedra, Fast approximations for sums of distances, clustering and the Fermat-Weber problem, Approximation and complexity of the capacitated geometric median problem

Cites Work