2026-07-26T05:31:58Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8856 2024-03-06T10:42:48Z ddc:004 open_access

A Greedy Algorithm for Subspace Approximation Problem Thang, Nguyen Kim Approximation Algorithms Subspace Approximation In the subspace approximation problem, given m points in R^{n} and an integer k <= n, the goal is to find a k-dimension subspace of R^{n} that minimizes the l_{p}-norm of the Euclidean distances to the given points. This problem generalizes several subspace approximation problems and has applications from statistics, machine learning, signal processing to biology. Deshpande et al. [Deshpande et al., 2011] gave a randomized O(sqrt{p})-approximation and this bound is proved to be tight assuming NP != P by Guruswami et al. [Guruswami et al., 2016]. It is an intriguing question of determining the performance guarantee of deterministic algorithms for the problem. In this paper, we present a simple deterministic O(sqrt{p})-approximation algorithm with also a simple analysis. That definitely settles the status of the problem in term of approximation up to a constant factor. Besides, the simplicity of the algorithm makes it practically appealing. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nguyen Kim Thang 2018 Is Part Of LIPIcs, Volume 101, 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2018.30 urn:nbn:de:0030-drops-88562 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2018.30 eng https://creativecommons.org/licenses/by/3.0/legalcode