MARC

 008250123s2024        us                              c    eng  d
■001000017161175
■00520250211151320
■006m          o    d                
■007cr#unu||||||||
■020    ▼a9798382841236
■035    ▼a(MiAaPQ)AAI31239159
■040    ▼aMiAaPQ▼cMiAaPQ
■0820  ▼a004
■1001  ▼aMirka,  Renee.▼0(orcid)0000-0003-1470-639X
■24510▼aOn  Graph  Coloring,  Max  Cut,  and  Semidefinite  Rank
■260    ▼a[Sl]▼bCornell  University▼c2024
■260  1▼aAnn  Arbor▼bProQuest  Dissertations  &  Theses▼c2024
■300    ▼a136  p
■500    ▼aSource:  Dissertations  Abstracts  International,  Volume:  85-12,  Section:  B.
■500    ▼aAdvisor:  Williamson,  David.
■5021  ▼aThesis  (Ph.D.)--Cornell  University,  2024.
■520    ▼aIn  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.
■590    ▼aSchool  code:  0058.
■650  4▼aComputer  science
■650  4▼aMathematics
■653    ▼aGraph  coloring
■653    ▼aMatrix  rank
■653    ▼aMax  cut
■653    ▼aSemidefinite  programming
■690    ▼a0984
■690    ▼a0796
■690    ▼a0405
■71020▼aCornell  University▼bComputer  Science.
■7730  ▼tDissertations  Abstracts  International▼g85-12B.
■790    ▼a0058
■791    ▼aPh.D.
■792    ▼a2024
■793    ▼aEnglish
■85640▼uhttp://www.riss.kr/pdu/ddodLink.do?id=T17161175▼nKERIS▼z이  자료의  원문은  한국교육학술정보원에서  제공합니다.

Preview

Export

ChatGPT Discussion

AI Recommended Related Books