ﻻ يوجد ملخص باللغة العربية
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.
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 i
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
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 o
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 tec
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-part