Yinyu Ye 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. Citation Working Paper, Department of Management Sciences, Henry, B. Tippie College of Business, The … Read more
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}. Citation Working Paper, MIT and the University of Iowa Article Download View A 1.52-Approximation Algorithm for the Uncapacitated Facility … Read more
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