MARC

 008260203s2023        us                              c    eng  d
■001000017366045
■00520260209102934
■006m          o    d                
■007cr#unu||||||||
■020    ▼a9798265405050
■035    ▼a(MiAaPQ)AAI32316143
■035    ▼a(MiAaPQ)GeorgiaTech72683
■040    ▼aMiAaPQ▼cMiAaPQ
■0820  ▼a500
■1001  ▼aChen,  Li.
■24510▼aHinted  Data  Structures  with  Applications  to  Optimization  and  Learning
■260    ▼a[Sl]▼bGeorgia  Institute  of  Technology▼c2023
■260  1▼aAnn  Arbor▼bProQuest  Dissertations  &  Theses▼c2023
■300    ▼a295  p
■500    ▼aSource:  Dissertations  Abstracts  International,  Volume:  87-05,  Section:  B.
■500    ▼aAdvisor:  Peng,  Richard.
■5021  ▼aThesis  (Ph.D.)--Georgia  Institute  of  Technology,  2023.
■520    ▼aThis  thesis  investigates  the  interplay  among  data  structures,  graph  algorithms,  and  machine  learning,  providing  a  fresh  lens  on  conventional  perspectives  concerning  worst-case  scenarios  and  data  structure  performance.  The  thesis  is  divided  into  two  main  parts.The  first  part  delves  into  the  concept  of  Low  Stretch  Decomposition  (LSD),  a  crucial  component  in  graph  algorithm  design.  The  study  applies  LSDs  to  devise  a  nearly  linear  time  algorithm  to  compute  the  terminal  state  of  graph  diffusions,  specifically  the  2-norm  flow  diffusion,  and  identify  local  clusters.  It  also  pioneers  the  examination  of  LSD  on  dynamic  graphs,  leading  to  the  creation  of  fully  dynamic  data  structures  for  computing  approximate  cuts  and  distances.The  second  part  of  the  thesis  explores  how  data  structures  leverage  'hints'  to  enhance  their  efficiency.  It  demonstrates  this  by  solving  maximum  flows  and  minimum-cost  flow  problems  using  dynamic  LSD  and  an  ℓ1  Interior  Point  Method  (IPM).  The  hints  derived  from  the  IPM  updates  expedite  the  data  structure  and  result  in  an  almost  linear  time  algorithm  for  the  problem.  This  section  also  delves  into  learning-augmented  B-trees,  which  benefit  from  advice  produced  by  machine  learning  models.Throughout  the  thesis,  a  comprehensive  understanding  of  how  optimization  algorithms  and  machine  learning  models  interact  with  data  structures  in  non-worst-case  and  non-adaptive  ways  is  pursued.
■590    ▼aSchool  code:  0078.
■650  4▼aDecomposition
■650  4▼aDiffusion
■650  4▼aGraphs
■650  4▼aOptimization  algorithms
■690    ▼a0800
■71020▼aGeorgia  Institute  of  Technology.
■7730  ▼tDissertations  Abstracts  International▼g87-05B.
■790    ▼a0078
■791    ▼aPh.D.
■792    ▼a2023
■793    ▼aEnglish
■85640▼uhttp://www.riss.kr/pdu/ddodLink.do?id=T17366045▼nKERIS▼z이  자료의  원문은  한국교육학술정보원에서  제공합니다.

Preview

Export

ChatGPT Discussion

AI Recommended Related Books