Upplösningssystem online (OCRS) föreslogs av Feldman, Svensson, och Zenklusen [FSZ16] som en generisk teknik för att runda en fraktionerad lösning i matroidpolytopen på ett online-sätt. Den har funnit applikationer i flera stokastiska kombinatoriska problem där det finns ett åtagande begränsning: på att se värdet av ett stokastiskt element, algoritmen måste omedelbart och oåterkalleligen besluta om att välja det samtidigt som alltid upprätthålla en oberoende uppsättning i matroiden. Även om OCRS omedelbart leder till profeten ojämlikhet, dessa profet ojämlikheter är inte optimal. Kan vi istället använda profeten ojämlikhet för att utforma optimala OCRS? Vi designar den första optimala 1/2-OCRS för matriser genom att minska problemet till att utforma en matris profet ojämlikhet där vi jämför med den starkare riktmärket för en ex-ante avkoppling. Vi introducerar och designar också optimal (1 − 1/e)-random ordning CRS för matroider, som liknar OCRS men ankomsten väljs enhetligt på måfå.
Lee och Singla REF konstruerade optimala 1 2 -OCRS och p1 ́1 e q-OCRS för matroider med godtycklig ordning respektive slumpmässig ordning.
Optimal Online Contention Resolution Schemes via Ex-Ante Prophet Inequalities
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}