Column Subset Selection Problem is UG-hard

作者：

Highlights：

• Select a subset of columns/rows of a matrix so that they represent the matrix well.

• Formulated as Column Subset Selection Problem and Column–Row Subset Selection Problem.

• Unique Games Conjecture implies that there is no PTAS.

• First complexity theoretic result of this kind for these problems.

摘要

•Select a subset of columns/rows of a matrix so that they represent the matrix well.•Formulated as Column Subset Selection Problem and Column–Row Subset Selection Problem.•Unique Games Conjecture implies that there is no PTAS.•First complexity theoretic result of this kind for these problems.

论文关键词：Matrices,Subset selection,Hardness,Unique Games Conjecture

论文评审过程：Received 12 June 2012, Revised 26 September 2012, Accepted 9 January 2014, Available online 16 January 2014.

论文官网地址：https://doi.org/10.1016/j.jcss.2014.01.004