Tata Institute of Fundamental Research
Integer Linear Programs and Local Search for Max-Cut (Author: Svatopluk Poljak)
STCS Student Seminar
Speaker:
Vidya Sagar Sharma
Organiser:
Kumar Saurav
Date:
Friday, 6 Mar 2020, 14:00 to 15:00
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
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: https://epubs.siam.org/doi/pdf/10.1137/S0097539793245350
| Speaker: | Vidya Sagar Sharma |
| Organiser: | Kumar Saurav |
| Date: | Friday, 6 Mar 2020, 14:00 to 15:00 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
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: https://epubs.siam.org/doi/pdf/10.1137/S0097539793245350
Paper Link: https://epubs.siam.org/doi/pdf/10.1137/S0097539793245350