Antonio De Rosa

Efficient Joint Object Matching via Linear Programming

  • Antonio De Rosa
  • Aida Khajavirad
    • Categories Cutting Plane Approaches, Integer Programming, Linear Programming Tags , , , ,

    Joint object matching, also known as multi-image matching, namely, the problem of finding consistent partial maps among all pairs of objects within a collection, is a crucial task in many areas of computer vision. This problem subsumes bipartite graph matching and graph partitioning as special cases and is NP-hard, in general. We develop scalable linear … Read more

    The ratio-cut polytope and K-means clustering

  • Antonio De Rosa
  • Aida Khajavirad
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches, Polyhedra Tags

    We introduce the ratio-cut polytope defined as the convex hull of ratio-cut vectors corresponding to all partitions of $n$ points in $\R^m$ into at most $K$ clusters. This polytope is closely related to the convex hull of the feasible region of a number of clustering problems such as K-means clustering and spectral clustering. We study … Read more