Sfaturi privind complexitatea algoritmilor de prioritate SpringerLink

Abstract

Modelul prioritar al algoritmilor „lacomi” a fost introdus de Borodin, Nielsen și Rackoff în 2002. Mărim acest model permițând algoritmilor prioritari să aibă acces la sfaturi, adică informații laterale precomputate de un oracol atotputernic. Obținerea unor limite inferioare în modelul prioritar fără sfaturi poate fi o provocare și poate implica argumente complicate ale adversarului. Deoarece modelul prioritar cu sfaturi este și mai puternic, obținerea unor limite inferioare prezintă dificultăți suplimentare. Evităm aceste dificultăți prin dezvoltarea unui cadru general de reduceri care face ca dovezile la limita inferioară să fie relativ simple și de rutină. Începem prin a introduce problema Pair Matching, pentru care suntem capabili să dovedim limite inferioare puternice în modelul prioritar cu sfaturi. Dezvoltăm un șablon pentru construirea unei reduceri de la potrivirea perechii la alte probleme din modelul prioritar cu sfaturi - această parte este dificilă din punct de vedere tehnic, deoarece reducerea trebuie să definească o funcție de prioritate validă pentru potrivirea perechii, respectând în același timp funcția de prioritate pentru cealaltă problemă. În cele din urmă, aplicăm șablonul pentru a obține limite inferioare pentru o serie de probleme standard de optimizare discretă.

---