School of Technology and Computer Science Seminars

Integer Linear Programs and Local Search for Max-Cut (Author: Svatopluk Poljak)

by Vidya Sagar Sharma (STCS, TIFR)

Friday, March 6, 2020 from to (Asia/Kolkata)
at A-201 (STCS Seminar Room)
Abstract: Schaffer and Yannakakis have shown that the max-cut problem with the FLIP neighborhood is polynomial-time local search (PLS) complete, and hence among the most difficult problems in the PLS class. The FLIP neighbourhood of a 2-partition is defined by moving a single vertex to the opposite class. In this paper, the author has shown that when restricted to the cubic graph, the FLIP local search becomes "easy" and finds a local max-cut in $O(n^2)$ steps.

Paper Link:
Organised by Kumar Saurav