The algebraic degree of geometric optimization problems

DOI10.1007/BF02187906zbMATH Open0647.90087DBLPjournals/dcg/Bajaj88OpenAlexW2071857538WikidataQ29307364 ScholiaQ29307364MaRDI QIDQ1104865FDOQ1104865

Authors: Chanderjit L. Bajaj 

Publication date: 1988

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

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

Recommendations

• Geometric optimization and the polynomial hierarchy
• scientific article; zbMATH DE number 3965441
• Geometric optimization and sums of algebraic functions
• Geometric optimization and sums of algebraic functions
• Geometric optimization and \(D^ P\)-completeness
• A special class of problems of geometric optimization
• Algebraic degree in semidefinite and polynomial optimization
• Publication:3199209
• Geometric methods and optimization problems

zbMATH Keywords

facility locationalgebraic degreeclassic Weber problemGalois methodsline-restricted Weber problem

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• The transitive groups of degree up to eleven⁺
• Title not available (Why is that?)
• The Determination of Galois Groups
• Title not available (Why is that?)
• Title not available (Why is that?)
• Polynomial Minimum Root Separation
• Title not available (Why is that?)
• Title not available (Why is that?)
• Some Remarks on Computing Galois Groups
• Title not available (Why is that?)
• Title not available (Why is that?)
• A Method to Compute Minimal Polynomials
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (55)

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

This page was built for publication: The algebraic degree of geometric optimization problems

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