Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userLocal approximation algorithms for a class of 0/1 max-min linear programs
96
0
0.0
(
0
)
Added by
Jukka Suomela
Publication date
2008
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We study the applicability of distributed, local algorithms to 0/1 max-min LPs where the objective is to maximise ${min_k sum_v c_{kv} x_v}$ subject to ${sum_v a_{iv} x_v le 1}$ for each $i$ and ${x_v ge 0}$ for each $v$. Here $c_{kv} in {0,1}$, $a_{iv} in {0,1}$, and the support sets ${V_i = {v : a_{iv} > 0 }}$ and ${V_k = {v : c_{kv}>0 }}$ have bounded size; in particular, we study the case $|V_k| le 2$. Each agent $v$ is responsible for choosing the value of $x_v$ based on information within its constant-size neighbourhood; the communication network is the hypergraph where the sets $V_k$ and $V_i$ constitute the hyperedges. We present a local approximation algorithm which achieves an approximation ratio arbitrarily close to the theoretical lower bound presented in prior work.
rate research
Read More
In a bipartite max-min LP, we are given a bipartite graph $myG = (V cup I cup K, E)$, where each agent $v in V$ is adjacent to exactly one constraint $i in I$ and exactly one objective $k in K$. Each agent $v$ controls a variable $x_v$. For each $i in I$ we have a nonnegative linear constraint on the variables of adjacent agents. For each $k in K$ we have a nonnegative linear objective function of the variables of adjacent agents. The task is to maximise the minimum of the objective functions. We study local algorithms where each agent $v$ must choose $x_v$ based on input within its constant-radius neighbourhood in $myG$. We show that for every $epsilon>0$ there exists a local algorithm achieving the approximation ratio ${Delta_I (1 - 1/Delta_K)} + epsilon$. We also show that this result is the best possible -- no local algorithm can achieve the approximation ratio ${Delta_I (1 - 1/Delta_K)}$. Here $Delta_I$ is the maximum degree of a vertex $i in I$, and $Delta_K$ is the maximum degree of a vertex $k in K$. As a methodological contribution, we introduce the technique of graph unfolding for the design of local approximation algorithms.
A local algorithm is a distributed algorithm where each node must operate solely based on the information that was available at system startup within a constant-size neighbourhood of the node. We study the applicability of local algorithms to max-min LPs where the objective is to maximise $min_k sum_v c_{kv} x_v$ subject to $sum_v a_{iv} x_v le 1$ for each $i$ and $x_v ge 0$ for each $v$. Here $c_{kv} ge 0$, $a_{iv} ge 0$, and the support sets $V_i = {v : a_{iv} > 0 }$, $V_k = {v : c_{kv}>0 }$, $I_v = {i : a_{iv} > 0 }$ and $K_v = {k : c_{kv} > 0 }$ have bounded size. In the distributed setting, each agent $v$ is responsible for choosing the value of $x_v$, and the communication network is a hypergraph $mathcal{H}$ where the sets $V_k$ and $V_i$ constitute the hyperedges. We present inapproximability results for a wide range of structural assumptions; for example, even if $|V_i|$ and $|V_k|$ are bounded by some constants larger than 2, there is no local approximation scheme. To contrast the negative results, we present a local approximation algorithm which achieves good approximation ratios if we can bound the relative growth of the vertex neighbourhoods in $mathcal{H}$.
We present a local algorithm (constant-time distributed algorithm) for approximating max-min LPs. The objective is to maximise $omega$ subject to $Ax le 1$, $Cx ge omega 1$, and $x ge 0$ for nonnegative matrices $A$ and $C$. The approximation ratio of our algorithm is the best possible for any local algorithm; there is a matching unconditional lower bound.
We show that the linear or quadratic 0/1 program[P:quadmin{ c^Tx+x^TFx : :A,x =b;:xin{0,1}^n},]can be formulated as a MAX-CUT problem whose associated graph is simply related to the matrices $F$ and $A^TA$.Hence the whole arsenal of approximation techniques for MAX-CUT can be applied. We also compare the lower boundof the resulting semidefinite (or Shor) relaxation with that of the standard LP-relaxation and the first semidefinite relaxationsassociated with the Lasserre hierarchy and the copositive formulations of $P$.
This paper presents an efficient parallel approximation scheme for a new class of min-max problems. The algorithm is derived from the matrix multiplicative weights update method and can be used to find near-optimal strategies for competitive two-party classical or quantum interactions in which a referee exchanges any number of messages with one party followed by any number of additional messages with the other. It considerably extends the class of interactions which admit parallel solutions, demonstrating for the first time the existence of a parallel algorithm for an interaction in which one party reacts adaptively to the other. As a consequence, we prove that several competing-provers complexity classes collapse to PSPACE such as QRG(2), SQG and two new classes called DIP and DQIP. A special case of our result is a parallel approximation scheme for a specific class of semidefinite programs whose feasible region consists of lists of semidefinite matrices that satisfy a transcript-like consistency condition. Applied to this special case, our algorithm yields a direct polynomial-space simulation of multi-message quantum interactive proofs resulting in a first-principles proof of QIP=PSPACE.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
