scientific article; zbMATH DE number 1775394
From MaRDI portal
Publication:4542527
zbMath1027.68979MaRDI QIDQ4542527
Satish B. Rao, Sanjeev Arora, Prabhakar Raghavan
Publication date: 17 September 2002
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Nonnumerical algorithms (68W05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Related Items
Linear-size universal discretization of geometric center-based problems in fixed dimensions ⋮ The two‐median problem on Manhattan meshes ⋮ A $$(1+{\varepsilon })$$ ( 1 + ε ) -Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs ⋮ New approximation algorithms for the unsplittable capacitated facility location problem ⋮ Clustering with or without the approximation ⋮ On the choice of aggregation points for continuous \(p\)-median problems: A case for the gravity centre ⋮ Preclustering algorithms for imprecise points ⋮ On the bounded-hop MST problem on random Euclidean instances ⋮ Approximation Algorithms for Buy-at-Bulk Geometric Network Design ⋮ Approximation schemes for node-weighted geometric Steiner tree problems ⋮ Clustering through continuous facility location problems ⋮ A local search approximation algorithm for \(k\)-means clustering ⋮ Incremental facility location problem and its competitive algorithms ⋮ A PTAS for the geometric connected facility location problem ⋮ Clustering and the perturbed spatial median ⋮ \(k\)-median: exact recovery in the extended stochastic ball model ⋮ Location, pricing and the problem of Apollonius ⋮ Universal Algorithms for Clustering Problems ⋮ On the complexity of some problems of searching for a family of disjoint clusters ⋮ A Modern View on Stability of Approximation ⋮ Unnamed Item ⋮ \(\mathrm{M}^p\)UFLP: universal facility location problem in the \(p\)-th power of metric space ⋮ An Approximation Algorithm for the Continuous k-Medians Problem in a Convex Polygon ⋮ Approximation algorithms for fair \(k\)-median problem without fairness violation ⋮ Complexity of some problems of quadratic partitioning of a finite set of points in Euclidean space into balanced clusters ⋮ A PTAS for the cardinality constrained covering with unit balls ⋮ A $(1+\varepsilon)$-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs ⋮ Data stability in clustering: a closer look ⋮ A Streaming Algorithm for k-Means with Approximate Coreset ⋮ Polynomial time approximation schemes for clustering in low highway dimension graphs ⋮ Local Search Yields a PTAS for $k$-Means in Doubling Metrics ⋮ Local Search Yields Approximation Schemes for $k$-Means and $k$-Median in Euclidean and Minor-Free Metrics ⋮ An Improved Competitive Algorithm for One-Dimensional Incremental Median Problem ⋮ Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension ⋮ Bounded-hop communication networks ⋮ Local search algorithms for the red-blue median problem ⋮ Approximating \(k\)-hop minimum spanning trees in Euclidean metrics ⋮ Faster balanced clusterings in high dimension ⋮ Facility location models for distribution system design ⋮ On Euclidean vehicle routing with allocation ⋮ Lossy kernelization of same-size clustering ⋮ Unnamed Item ⋮ On efficient connectivity-preserving transformations in a grid ⋮ Some Estimates on the Discretization of Geometric Center-Based Problems in High Dimensions ⋮ Unnamed Item ⋮ A systematic approach to bound factor-revealing LPs and its application to the metric and squared metric facility location problems ⋮ The Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme ⋮ Continuous reformulations and heuristics for the Euclidean travelling salesperson problem ⋮ Center-based clustering under perturbation stability ⋮ Interactive Clustering of Linear Classes and Cryptographic Lower Bounds ⋮ Minimizing the sum of distances to a server in a constraint network ⋮ Sublinear‐time approximation algorithms for clustering via random sampling ⋮ The traveling \(k\)-median problem: approximating optimal network coverage ⋮ Facility Location with Matroid or Knapsack Constraints ⋮ Lossy kernelization of same-size clustering ⋮ Probabilistic \(k\)-median clustering in data streams ⋮ A constant-factor approximation algorithm for the \(k\)-median problem
