Name
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 that 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 rewards are sampled from a distribution. Our aim is to identify sufficient conditions on the network structure and rewards distributions to guarantee average-case polynomiality of the underlying optimization problem. Additionally, we wish to characterize the efficiency of a decentralized solution generated on the basis of local information. We construct a new decentralized algorithm called Cavity Expansion and establish its theoretical performance for a variety of graph models and reward function distributions. Specifically, for certain classes of models we prove that our algorithm is able to find a near-optimal solution with high probability in a decentralized way. The success of the algorithm is based on the network exhibiting a certain correlation decay (long-range independence) property, and we prove that this property is indeed exhibited by the models of interest. 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. Yet we show that the closely related Maximum Weight Independent Set problem for the same class of graphs admits a PTAS when the weights are independently and identically distributed with the exponential distribution. Namely, randomization of the reward function turns an NP-hard problem into a tractable one. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1287/moor.2013.0609 | MATHEMATICS OF OPERATIONS RESEARCH |
Keywords | DocType | Volume |
optimization,NP-hardness,long-range independence | Journal | 39 |
Issue | ISSN | Citations |
2 | 0364-765X | 4 |
PageRank | References | Authors |
0.49 | 21 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| DAVID GAMARNIK | 1 | 641 | 61.04 |
| David A. Goldberg | 2 | 21 | 2.32 |
| Theophane Weber | 3 | 159 | 16.79 |