approximation

Approximating K-means-type clustering via semidefinite programming

  • Jiming Peng
  • Yu Wei
    • Categories Approximation Algorithms, Convex Optimization, Data-Mining Tags , , ,

    One of the fundamental clustering problems is to assign $n$ points into $k$ clusters based on the minimal sum-of-squares(MSSC), which is known to be NP-hard. In this paper, by using matrix arguments, we first model MSSC as a so-called 0-1 semidefinite programming (SDP). We show that our 0-1 SDP model provides an unified framework for … Read more

    Geometrical Heuristics for Multiprocessor Flowshop Scheduling with Uniform Machines at Each Stage

  • S.V. Sevastianov
    • Categories Scheduling Tags , , ,

    We consider the multi-stage multiprocessor flowshop scheduling problem with uniform machines at each stage and the minimum makespan objective. Using a vector summation technique, three polynomial-time heuristics are developed with absolute worst-case performance guarantees. As a direct corollary, in the special case of the ordinary flowshop problem we come to the best approximation algorithms (both … Read more