Publication Type
Conference Proceeding Article
Version
publishedVersion
Publication Date
7-2014
Abstract
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.
Discipline
Computer Sciences | Theory and Algorithms
Publication
Proceedings of the Twenty-eighth AAAI Conference On Artificial Intelligence and the Twenty-sixth Innovative Applications of Artificial Intelligence Conference
Volume
3
First Page
2308
Last Page
2314
ISBN
9781577356790
Publisher
AI Access Foundation
City or Country
Quebec City
Citation
KUMAR, T. K. Satish; NGUYEN DUC THIEN; YEOH, William; and KOENIG, Sven.
A simple polynomial-time randomized distributed algorithm for connected row convex constraints. (2014). Proceedings of the Twenty-eighth AAAI Conference On Artificial Intelligence and the Twenty-sixth Innovative Applications of Artificial Intelligence Conference. 3, 2308-2314.
Available at: https://ink.library.smu.edu.sg/sis_research/3464
Copyright Owner and License
LARC
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Additional URL
http://dl.acm.org/citation.cfm?id=2892872