MARC

 008260126s2024        us                              c    eng  d
■001000017361076
■00520260202105702
■006m          o    d                
■007cr#unu||||||||
■020    ▼a9798263307981
■035    ▼a(MiAaPQ)AAI32409885
■035    ▼a(MiAaPQ)124363
■040    ▼aMiAaPQ▼cMiAaPQ
■0820  ▼a004
■1001  ▼aLivanos,  Vasilis.
■24510▼aOptimal  Stopping  Problems  and  Combinatorial  Optimization  Under  Uncertainty
■260    ▼a[Sl]▼bUniversity  of  Illinois  at  Urbana-Champaign▼c2024
■260  1▼aAnn  Arbor▼bProQuest  Dissertations  &  Theses▼c2024
■300    ▼a122  p
■500    ▼aSource:  Dissertations  Abstracts  International,  Volume:  87-05,  Section:  B.
■500    ▼aAdvisor:  Mehta,  Ruta.
■5021  ▼aThesis  (Ph.D.)--University  of  Illinois  at  Urbana-Champaign,  2024.
■520    ▼aThis  thesis  studies  optimal  stopping  and  combinatorial  optimization  problems  in  an  uncertain  environment.  Optimal  stopping  captures  many  natural  scenarios  in  which  decisions  have  to  be  made  without  knowledge  of  the  future  and  cannot  be  amended  later  on.  In  combinatorial  optimization  settings  the  objective  is  to  optimize  a  function  over  distinct  elements  subject  to  certain  feasibility  constraints.Combinatorial  optimization  has  been  classically  studied  in  the  full-information  setting  where  the  entire  input  is  known  a  priori.  Combining  combinatorial  optimization  with  an  uncertain  environment  leads  to  settings  in  which  algorithms  have  only  partial  knowledge  of  the  input,  which  is  revealed  element-by-element  and  all  decisions  of  an  algorithm  have  to  be  immediate  and  irrevocable.  Such  settings  of  optimization  under  uncertainty  arise  naturally  in  applications  in  which  knowledge  of  the  future  cannot  be  obtained,  either  inherently  or  due  to  prohibiting  costs  or  noise.In  this  thesis  we  focus  on  two  settings.  The  first  is  a  classical  model  in  optimal  stopping  theory,  the  prophet  inequality,  in  which  an  algorithm  has  to  pick  one  of  many  random  variables  whose  realizations  are  observed  sequentially  and  compares  against  a  prophet  who  knows  all  realizations  in  advance.  The  second  setting  is  rounding  a  solution  to  a  linear  program  in  an  online  manner  via  the  use  of  an  Online  Contention  Resolution  Scheme  (OCRS)  which  is  very  useful  in  settings  of  combinatorial  optimization  under  uncertainty.We  initiate  the  study  of  prophet  inequalities  for  independent  and  identically  distributed  (I.I.D.)  random  variables  for  cost  minimization,  showing  distribution-dependent  constant-factor  guarantees  for  the  competitive  ratio  that  are  qualitatively  different  from  the  maximization  setting.  In  addition,  we  unify  the  maximization  and  minimization  I.I.D.  prophet  inequalities  via  the  theory  of  extreme  values  and  show  that  the  competitive  ratio  of  both  settings  is  governed  by  a  single  function  that  depends  only  on  the  extreme  value  index.  We  also  obtain  similar  results  for  the  objective  of  competition  complexity,  which  captures  how  many  more  random  variables  an  algorithm  needs  to  observe  in  order  to  beat  the  prophet.We  then  ask  how  our  guarantees  change  if  we  allow  our  algorithms  the  ability  to  ask  simple  questions  to  an  oracle  that  has  knowledge  of  the  future.  Motivating  this,  we  establish  an  equivalence  between  this  setting  and  the  top-1-of-m  setting  in  which  the  algorithm  can  select  m  values  but  is  judged  only  for  the  best  one  among  them.  For  the  oracle-augmented  model,  we  obtain  guarantees  on  the  competitive  ratio  and  the  probability  of  selecting  the  maximum  realization  that  are  almost  tight  asymptotically  with  respect  to  the  number  of  oracle  calls,  for  both  the  I.I.D.  case  and  the  case  of  non-identical  random  variables  whose  arrival  order  is  controlled  by  an  adversary.Afterwards,  we  turn  to  more  general  combinatorial  optimization  settings  where  multiple  elements  can  be  selected.  We  design  optimal  greedy  OCRSs  for  special  cases  of  matroids  and  provide  matching  upper  bounds  to  show  their  optimality.  We  then  use  greedy  OCRSs  to  obtain  algorithms  with  significantly  improved  guarantees  on  the  competitive  ratio  for  prophet  inequalities  with  a  submodular  objective  function  under  several  combinatorial  feasibility  constraints  such  as  matroids,  matchings  and  knapsacks.
■590    ▼aSchool  code:  0090.
■650  4▼aComputer  science
■650  4▼aApplied  mathematics
■650  4▼aInformation  technology
■653    ▼aProphet  inequalities
■653    ▼aContention  Resolution  Schemes
■653    ▼aOnline  selection
■653    ▼aCombinatorial  optimization
■653    ▼aExtreme  Value  Theory
■690    ▼a0984
■690    ▼a0489
■690    ▼a0364
■71020▼aUniversity  of  Illinois  at  Urbana-Champaign▼bComputer  Science.
■7730  ▼tDissertations  Abstracts  International▼g87-05B.
■790    ▼a0090
■791    ▼aPh.D.
■792    ▼a2024
■793    ▼aEnglish
■85640▼uhttp://www.riss.kr/pdu/ddodLink.do?id=T17361076▼nKERIS▼z이  자료의  원문은  한국교육학술정보원에서  제공합니다.

미리보기

내보내기

chatGPT토론

Ai 추천 관련 도서