A Simple Polynomial-Time Randomized Distributed Algorithm for Connected Row Convex Constraints
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.
Cite
Text
Kumar et al. "A Simple Polynomial-Time Randomized Distributed Algorithm for Connected Row Convex Constraints." AAAI Conference on Artificial Intelligence, 2014. doi:10.1609/AAAI.V28I1.9043Markdown
[Kumar et al. "A Simple Polynomial-Time Randomized Distributed Algorithm for Connected Row Convex Constraints." AAAI Conference on Artificial Intelligence, 2014.](https://mlanthology.org/aaai/2014/kumar2014aaai-simple/) doi:10.1609/AAAI.V28I1.9043BibTeX
@inproceedings{kumar2014aaai-simple,
title = {{A Simple Polynomial-Time Randomized Distributed Algorithm for Connected Row Convex Constraints}},
author = {Kumar, T. K. Satish and Nguyen, Duc Thien and Yeoh, William and Koenig, Sven},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2014},
pages = {2308-2314},
doi = {10.1609/AAAI.V28I1.9043},
url = {https://mlanthology.org/aaai/2014/kumar2014aaai-simple/}
}