Correlation decay in random decision networks

DOI10.1287/MOOR.2013.0609zbMATH Open1291.90047arXiv0912.0338OpenAlexW2963083065MaRDI QIDQ5169700FDOQ5169700

Authors: David Gamarnik, David A. Goldberg, Theophane Weber 

Publication date: 11 July 2014

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Abstract: We consider a decision network on an undirected graph in which each node corresponds to a decision variable, and each node and edge of the graph is associated with a reward function whose value depends only on the variables of the corresponding nodes. The goal is to construct a decision vector which maximizes the total reward. This decision problem encompasses a variety of models, including maximum-likelihood inference in graphical models (Markov Random Fields), combinatorial optimization on graphs, economic team theory and statistical physics. The network is endowed with a probabilistic structure in which costs are sampled from a distribution. Our aim is to identify sufficient conditions to guarantee average-case polynomiality of the underlying optimization problem. We construct a new decentralized algorithm called Cavity Expansion and establish its theoretical performance for a variety of models. Specifically, for certain classes of models we prove that our algorithm is able to find near optimal solutions with high probability in a decentralized way. The success of the algorithm is based on the network exhibiting a correlation decay (long-range independence) property. Our results have the following surprising implications in the area of average case complexity of algorithms. Finding the largest independent (stable) set of a graph is a well known NP-hard optimization problem for which no polynomial time approximation scheme is possible even for graphs with largest connectivity equal to three, unless P=NP. We show that the closely related maximum weighted independent set problem for the same class of graphs admits a PTAS when the weights are i.i.d. with the exponential distribution. Namely, randomization of the reward function turns an NP-hard problem into a tractable one.

Full work available at URL: https://arxiv.org/abs/0912.0338

Recommendations

• scientific article; zbMATH DE number 6297706
• On the complexity of decentralized decision making and detection problems
• An Approximation Algorithm for the Discrete Team Decision Problem
• Correlation decay and deterministic FPTAS for counting colorings of a graph
• Approximate counting via correlation decay in spin systems

zbMATH Keywords

optimizationNP-hardnesslong-range independence

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Approximation algorithms (68W25) Stochastic network models in operations research (90B15)

Cited In (4)

• Scalable Reinforcement Learning for Multiagent Networked Systems
• Near-Optimal Distributed Linear-Quadratic Regulator for Networked Systems
• Online discrete optimization in social networks in the presence of Knightian uncertainty
• Asymptotic optimality of constant-order policies for lost sales inventory models with large lead times

This page was built for publication: Correlation decay in random decision networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5169700)