E-viri
Recenzirano
-
Mirka, Renee; Williamson, David P.
Operations research letters, March 2024, 2024-03-00, Letnik: 53Journal Article
This paper considers the relationship between semidefinite programs (SDPs), matrix rank, and maximum cuts of graphs. Utilizing complementary slackness conditions for SDPs, we investigate when the rank 1 feasible solution corresponding to a max cut is the unique optimal solution to the Goemans-Williamson max cut SDP by showing the existence of an optimal dual solution with rank n−1. Our results consider connected bipartite graphs and graphs with multiple max cuts. We conclude with a conjecture for general graphs.
