Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userTight local approximation results for max-min linear programs
115
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
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.
rate research
Read More
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 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.
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}$.
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.
Asadpour, Feige, and Saberi proved that the integrality gap of the configuration LP for the restricted max-min allocation problem is at most $4$. However, their proof does not give a polynomial-time approximation algorithm. A lot of efforts have been devoted to designing an efficient algorithm whose approximation ratio can match this upper bound for the integrality gap. In ICALP 2018, we present a $(6 + delta)$-approximation algorithm where $delta$ can be any positive constant, and there is still a gap of roughly $2$. In this paper, we narrow the gap significantly by proposing a $(4+delta)$-approximation algorithm where $delta$ can be any positive constant. The approximation ratio is with respect to the optimal value of the configuration LP, and the running time is $mathit{poly}(m,n)cdot n^{mathit{poly}(frac{1}{delta})}$ where $n$ is the number of players and $m$ is the number of resources. We also improve the upper bound for the integrality gap of the configuration LP to $3 + frac{21}{26} approx 3.808$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
