Abstract-Contention system har visat sig vara ett otroligt kraftfullt koncept som gör det möjligt att hantera en bred klass av problem. Ramverket har ursprungligen utformats för att hantera submodulära optimeringar under olika typer av begränsningar, det vill säga korsningar av utbytessystem (inklusive matroider), knapsacker och osplitterbara flöden på träd. Senare visade det sig att denna ram perfekt sträcker sig till optimering under osäkerhet, som stokastisk undersökning och online urvalsproblem, som ytterligare kan tillämpas på mekanismdesign. Vi lägger till den här raden av arbete genom att visa hur man skapar tvistelösningssystem för skärningspunkten mellan matriser och knapsacks när vi arbetar i slumpmässig ordning inställning. Mer exakt, vi känner till hela universum av element i förväg, men de visas i en ordning som ges av en slumpmässig permutation. Vid ankomsten måste vi oåterkalleligen besluta om vi ska ta ett element eller inte. Vi tar med en ny teknik för att analysera procedurer i slumpmässig ordning som bygger på martingaleteorin. Detta enhetliga tillvägagångssätt gör det lättare att kombinera begränsningar, och vi behöver inte förlita oss på entonigheterna i systemen för tvistelösning, vilket var fallet tidigare. Vårt papper fyller luckorna, utvidgar och skapar kopplingar mellan många tidigare resultat och tekniker. Den huvudsakliga tillämpningen av vårt ramverk är en k + 4 + ε approximation ratio för Bayesian multi-parameter unit-demand mekanism design under begränsningen av k matroids skärningspunkt, vilket förbättrar på de tidigare gränserna av 4k − 2 och e(k + 1). Andra resultat inkluderar förbättrade approximationskvoter för stokastisk k-set förpackning och submodulär stokastisk probing över godtyckliga icke-negativa submodulära objektiv funktion, medan tidigare resultat krävde målet att vara monoton.
Adamczyk och Wlodarczyk REF beaktade slumpmässig ordning modell och konstruerade 1 k`1 -OCRS för skärningspunkter av k matriser.
Random Order Contention Resolution Schemes
{'venue': '2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)', 'journal': '2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)', 'mag_field_of_study': ['Computer Science', 'Mathematics']}