Stochastic k-center and j-flat-center problems

DOI10.1137/1.9781611974782.8MaRDI QIDQ4575742zbMATH OpenOpenAlexFDO

Authors Lingxiao Huang, Jian Li

Publication date 16 July 2018

Published in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1607.04989

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Stochastic programming (90C15)

Abstract: Solving geometric optimization problems over uncertain data have become increasingly important in many applications and have attracted a lot of attentions in recent years. In this paper, we study two important geometric optimization problems, the $k$-center problem and the $j$-flat-center problem, over stochastic/uncertain data points in Euclidean spaces. For the stochastic $k$-center problem, we would like to find $k$ points in a fixed dimensional Euclidean space, such that the expected value of the $k$-center objective is minimized. For the stochastic $j$-flat-center problem, we seek a $j$-flat (i.e., a $j$-dimensional affine subspace) such that the expected value of the maximum distance from any point to the $j$-flat is minimized. We consider both problems under two popular stochastic geometric models, the existential uncertainty model, where the existence of each point may be uncertain, and the locational uncertainty model, where the location of each point may be uncertain. We provide the first PTAS (Polynomial Time Approximation Scheme) for both problems under the two models. Our results generalize the previous results for stochastic minimum enclosing ball and stochastic enclosing cylinder.

Recommendations

• One-dimensional \(k\)-center on uncertain data
• One-dimensional \(k\)-center on uncertain data
• Clustering geometrically-modeled points in the aggregated uncertainty model
• The two-center problem of uncertain points on a real line
• Approximating the Expected Values for Combinatorial Optimization Problems over Stochastic Points

Cited in

(17)

• On the separability of stochastic geometric objects, with applications
• Exploiting flat subspaces in local search for \(p\)-center problem and two fault-tolerant variants
• Computing \(k\)-centers of uncertain points on a real line
• The two-center problem of uncertain points on a real line
• A Lottery Model for Center-Type Problems With Outliers
• Probabilistic smallest enclosing ball in high dimensions via subgradient sampling
• An \(O(n\log n)\)-time algorithm for the \(k\)-center problem in trees
• Approximation algorithms for stochastic clustering
• The Problem K-Means and Given J-Centers: Polynomial Solvability in One Dimension
• An O(n n)-time algorithm for the k-center problem in trees
• Clustering geometrically-modeled points in the aggregated uncertainty model
• Clustering with faulty centers
• Computing the center of uncertain points on cactus graphs
• The two-center problem of uncertain points on trees
• Computing the center of uncertain points on cactus graphs
• The two-center problem of uncertain points on cactus graphs
• The k-center problem of uncertain points on graphs

This page was built for publication: Stochastic \(k\)-center and \(j\)-flat-center problems

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