Jiawei Zhang

A Multi-Exchange Local Search Algorithm for the Capacitated Facility Location Problem

  • Bo Chen
  • Yinyu Ye
  • Jiawei Zhang
    • Categories Approximation Algorithms, Network Optimization Tags , ,

    We present a multi-exchange local search algorithm for approximating the capacitated facility location problem (CFLP), where a new local improvement operation is introduced that possibly exchanges multiple facilities simultaneously. We give a tight analysis for our algorithm and show that the performance guarantee of the algorithm is between $3+2\sqrt{2}-\epsilon$ and $3+2\sqrt{2}+\epsilon$ for any given constant … Read more

    Approximating the Two-Level Facility Location Problem Via a Quasi-Greedy Approach

  • Jiawei Zhang
    • Categories Approximation Algorithms Tags , ,

    We propose a {\em quasi-greedy} algorithm for approximating the classical uncapacitated $2$-level facility location problem ($2$-LFLP). Our algorithm, unlike the standard greedy algorithm, selects a sub-optimal candidate at each step. It also relates the minimization $2$-LFLP problem, in an interesting way, to the maximization version of the single level facility location problem. Another feature of … Read more

    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