Yinyu Ye

A Note on Approximating the 2-Catalog Segmentation Problem

  • Dachuan Xu
  • Yinyu Ye
  • Jiawei Zhang
    • Categories Approximation Algorithms, Combinatorial Optimization, Linear, Cone and Semidefinite Programming Tags ,

    We present a $.73$-approximation algorithm for a disjoint $2$-Catalog Segmentation and $.63$-approximation algorithm for the joint version of the problem. Previously best known results are $.65$ and $.56$, respectively. The results are based on semidefinite programming and a subtle rounding method. CitationWorking Paper, Department of Management Sciences, Henry, B. Tippie College of Business, The University … Read more

    A 1.52-Approximation Algorithm for the Uncapacitated Facility Location Problem

  • Mohammad Mahdian
  • Yinyu Ye
  • Jiawei Zhang
    • Categories Applications - OR and Management Sciences, Production and Logistics, Supply Chain Management Tags

    In this note we present an improved approximation algorithm for the (uncapacitated) metric facility location problem. This algorithm uses the idea of cost scaling, the greedy algorithm of \cite{JMS}, and the greedy augmentation procedure of \cite{CG,GK}. CitationWorking Paper, MIT and the University of IowaArticleDownload View PDF

    New Results on Quadratic Minimization

  • Yinyu Ye
  • Shuzhong Zhang
    • Categories Quadratic Programming, Semi-definite Programming Tags , ,

    In this paper we present several new results on minimizing an indefinite quadratic function under quadratic/linear constraints. The emphasis is placed on the case where the constraints are two quadratic inequalities. This formulation is known as {\em the extended trust region subproblem}\/ and the computational complexity of this problem is still unknown. We consider several … Read more