Asymptoticky optimální lineární algoritmus pro lokálně konzistentní CSP

Abstrakt

Ukazujeme optimální randomizovaný lineární algoritmus pro lokálně konzistentní CSP s binárními omezujícími podmínkami a dokazujeme, že tento algoritmus může být derandomizován.

Klíčová slova

• asymptotically
• optimal
• linear-time
• algorithm
• locally
• consistent
• constraint
• satisfaction
• problems