-
作者：d'Aspremont, Alexandre; Bach, Francis; El Ghaoui, Laurent
作者单位：Universite PSL; Ecole Normale Superieure (ENS); Centre National de la Recherche Scientifique (CNRS); Centre National de la Recherche Scientifique (CNRS); CNRS - Institute for Information Sciences & Technologies (INS2I); Universite PSL; Ecole Normale Superieure (ENS); Inria; University of California System; University of California Berkeley
摘要：We produce approximation bounds on a semidefinite programming relaxation for sparse principal component analysis. The sparse maximum eigenvalue problem cannot be efficiently approximated up to a constant approximation ratio, so our bounds depend on the optimum value of the semidefinite relaxation: the higher this value, the better the approximation. In particular, these bounds allow us to control approximation ratios for tractable statistics in hypothesis testing problems where data points are...
-
作者：Brunsch, Tobias; Roeglin, Heiko; Rutten, Cyriel; Vredeveld, Tjark
作者单位：University of Bonn; Maastricht University
摘要：We study popular local search and greedy algorithms for standard machine scheduling problems. The performance guarantee of these algorithms is well understood, but the worst-case lower bounds seem somewhat contrived and it is questionable whether they arise in practical applications. To find out how robust these bounds are, we study the algorithms in the framework of smoothed analysis, in which instances are subject to some degree of random noise. While the lower bounds for all scheduling vari...
-
作者：Ding, Chao; Sun, Defeng; Toh, Kim-Chuan
作者单位：Chinese Academy of Sciences; National University of Singapore; National University of Singapore
摘要：In this paper, we define a class of linear conic programming (which we call matrix cone programming or MCP) involving the epigraphs of five commonly used matrix norms and the well studied symmetric cone. MCP has recently been found to have many important applications, for example, in nuclear norm relaxations of affine rank minimization problems. In order to make the defined MCP tractable and meaningful, we must first understand the structure of these epigraphs. So far, only the epigraph of the...
-
作者：Epstein, Leah; Levin, Asaf
作者单位：University of Haifa; Technion Israel Institute of Technology
摘要：We consider basic problems of non-preemptive scheduling on uniformly related machines. For a given schedule, defined by a partition of the jobs into m subsets corresponding to the m machines, denotes the completion time of machine i. Our goal is to find a schedule that minimizes or maximizes for a fixed value of p such that . For the minimization problem is equivalent to the well-known problem of minimizing the norm of the vector of the completion times of the machines, and for , the maximizat...
