자료유형  

 학위논문

Control Number  

0017161175

International Standard Book Number  

9798382841236

Dewey Decimal Classification Number  

004

Main Entry-Personal Name  

Mirka, Renee.

Publication, Distribution, etc. (Imprint  

[S.l.] : Cornell University., 2024

Publication, Distribution, etc. (Imprint  

Ann Arbor : ProQuest Dissertations & Theses, 2024

Physical Description  

136 p.

General Note  

Source: Dissertations Abstracts International, Volume: 85-12, Section: B.

General Note  

Advisor: Williamson, David.

Dissertation Note  

Thesis (Ph.D.)--Cornell University, 2024.

Summary, Etc.  

요약In this thesis, we will focus on two of Karp's original NP-complete problems, graph coloring and max cut, both of which have established semidefinite programming relaxations. We introduce the use of semidefinite programming complementary slackness conditions to understand when an optimal solution to one of these SDP relaxations can be guaranteed to take the form of an optimal solution to the original problem. First, we consider the interplay between semidefinite programming, matrix rank, and graph coloring. Karger, Motwani, and Sudan give a vector program in which a coloring of a graph can be encoded as a semidefinite matrix of low rank. By complementary slackness conditions of semidefinite programming, if an optimal dual solution has high rank, any optimal primal solution must have low rank. In the case of the original Karger, Motwani, and Sudan vector program, we show that any graph which is a k-tree has sufficiently high dual rank, and we can extract the coloring from the corresponding low-rank primal solution. We can also show that if a graph is not uniquely colorable, then no sufficiently high rank dual optimal solution can exist.We then modify the semidefinite program to have an objective function with costs, and explore when we can create an objective function such that the optimal dual solution has sufficiently high rank. We show that it is always possible to construct such an objective function given the graph coloring. The construction of the objective function gives rise to heuristics for 4-coloring planar graphs which we also present. We enumerated all maximal planar graphs with an induced K4 of up to 14 vertices; the heuristics successfully found a 4-coloring for 99.75\\% of them.Then we switch settings to max cut. 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. We show in the case of connected bipartite graphs that they have sufficiently high dual rank. Analogously to graph coloring, we also show that if the max cut of a graph is not unique, then there cannot exist an optimal dual solution of sufficiently high rank. We conclude with a theorem and corresponding conjecture for general graphs.Finally, we switch to an experimental perspective and evaluate the performance of several max cut approximation algorithms. In particular, we compare the results of the Goemans and Williamson algorithm using semidefinite programming with Trevisan's algorithm using spectral partitioning. The former algorithm has a known .878 approximation guarantee whereas the latter has a .614 approximation guarantee. We investigate whether this gap in approximation guarantees is evident in practice or whether the spectral algorithm performs as well as the SDP. We also compare the performances to the standard greedy max cut algorithm which has a .5 approximation guarantee, two additional spectral algorithms, and a heuristic from Burer, Monteiro, and Zhang. The algorithms are tested on Erdos-Renyi random graphs, complete graphs from TSPLIB, and real-world graphs from the Network Repository. We find, unsurprisingly, that the spectral algorithms provide a significant speed advantage over the SDP. In our experiments, the spectral algorithms and BMZ heuristic return cuts with values which are competitive with those of the SDP.

Subject Added Entry-Topical Term  

Computer science.

Subject Added Entry-Topical Term  

Mathematics.

Index Term-Uncontrolled  

Graph coloring

Index Term-Uncontrolled  

Matrix rank

Index Term-Uncontrolled  

Max cut

Index Term-Uncontrolled  

Semidefinite programming

Added Entry-Corporate Name  

Cornell University Computer Science

Host Item Entry  

Dissertations Abstracts International. 85-12B.

Electronic Location and Access  

로그인을 한후 보실 수 있는 자료입니다.

Control Number  

joongbu:654264