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