A simple polynomial-time randomized distributed algorithm for connected row convex constraints

• Main Authors: KUMAR, T. K. Satish, NGUYEN DUC THIEN, YEOH, William, KOENIG, Sven
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2014
• Subjects: Computer Sciences; Theory and Algorithms
• Online Access: https://ink.library.smu.edu.sg/sis_research/3464; https://ink.library.smu.edu.sg/context/sis_research/article/4465/viewcontent/C110___A_Simple_Polynomial_Time_Randomized_Distributed_Algorithm_for_Connected_Row_Convex_Constraints__AAAI2014_.pdf
• Institution: Singapore Management University

In this paper, we describe a simple randomized algorithm that runs in polynomial time and solves connected row convex (CRC) constraints in distributed settings. CRC constraints generalize many known tractable classes of constraints like 2-SAT and implicational constraints. They can model problems in many domains including temporal reasoning and geometric reasoning, and generally speaking, play the role of "Gaussians" in the logical world. Our simple randomized algorithm for solving them in distributed settings, therefore, has a number of important applications. We support our claims through a theoretical analysis and empirical results.