Vi undersöker gapet mellan teori och praktik för exakt förgrening algoritmer. I teorin, gren-och-minska algoritmer för närvarande har den bästa tiden komplexitet för många viktiga problem. Å andra sidan, i praktiken, state-of-the-art metoder bygger på olika tillvägagångssätt, och den empiriska effektiviteten av sådana teoretiska algoritmer har sällan undersökts förmodligen eftersom de är till synes ineffektiva på grund av den uppsjö av komplexa reduktionsregler. I denna uppsats utformar vi en gren-och-reduce algoritm för vertex cover problem med hjälp av de tekniker som utvecklats för teoretiska algoritmer och jämföra dess praktiska prestanda med andra state-of-the-art empiriska metoder. Resultaten visar att gren-och-reducerade algoritmer faktiskt är ganska praktiska och konkurrenskraftiga med andra state-of-art metoder för flera typer av fall, vilket visar den praktiska effekten av teoretisk forskning på grenning algoritmer.
Akiba och Iwata REF var de första att visa effektiviteten av gren-och-reduce metoden för att lösa minimalt vertex cover problem i praktiken för stora glesa verkliga grafer.
Branch-and-Reduce Exponential/FPT Algorithms in Practice: A Case Study of Vertex Cover
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}