Correlation decay in random decision networks

DOI10.1287/MOOR.2013.0609MaRDI QIDQ5169700zbMATHOpenAlexFDO

Authors David Gamarnik, David A. Goldberg, Theophane Weber

Publication date 11 July 2014

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

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

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)

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.

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

Cited in

(4)

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

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)