Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userIntegrality Gap of the Configuration LP for the Restricted Max-Min Fair Allocation
105
0
0.0
(
0
)
Added by
Yuchen Mao
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
The max-min fair allocation problem seeks an allocation of resources to players that maximizes the minimum total value obtained by any player. Each player $p$ has a non-negative value $v_{pr}$ on resource $r$. In the restricted case, we have $v_{pr}in {v_r, 0}$. That is, a resource $r$ is worth value $v_r$ for the players who desire it and value 0 for the other players. In this paper, we consider the configuration LP, a linear programming relaxation for the restricted problem. The integrality gap of the configuration LP is at least $2$. Asadpour, Feige, and Saberi proved an upper bound of $4$. We improve the upper bound to $23/6$ using the dual of the configuration LP. Since the configuration LP can be solved to any desired accuracy $delta$ in polynomial time, our result leads to a polynomial-time algorithm which estimates the optimal value within a factor of $23/6+delta$.
rate research
Read More
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$.
The restricted max-min fair allocation problem seeks an allocation of resources to players that maximizes the minimum total value obtained by any player. It is NP-hard to approximate the problem to a ratio less than 2. Comparing the current best algorithm for estimating the optimal value with the current best for constructing an allocation, there is quite a gap between the ratios that can be achieved in polynomial time: roughly 4 for estimation and roughly $6 + 2sqrt{10}$ for construction. We propose an algorithm that constructs an allocation with value within a factor of $6 + delta$ from the optimum for any constant $delta > 0$. The running time is polynomial in the input size for any constant $delta$ chosen.
We study a delay-sensitive information flow problem where a source streams information to a sink over a directed graph G(V,E) at a fixed rate R possibly using multiple paths to minimize the maximum end-to-end delay, denoted as the Min-Max-Delay problem. Transmission over an edge incurs a constant delay within the capacity. We prove that Min-Max-Delay is weakly NP-complete, and demonstrate that it becomes strongly NP-complete if we require integer flow solution. We propose an optimal pseudo-polynomial time algorithm for Min-Max-Delay, with time complexity O(log (Nd_{max}) (N^5d_{max}^{2.5})(log R+N^2d_{max}log(N^2d_{max}))), where N = max{|V|,|E|} and d_{max} is the maximum edge delay. Besides, we show that the integrality gap, which is defined as the ratio of the maximum delay of an optimal integer flow to the maximum delay of an optimal fractional flow, could be arbitrarily large.
In this paper we present a new data structure for double ended priority queue, called min-max fine heap, which combines the techniques used in fine heap and traditional min-max heap. The standard operations on this proposed structure are also presented, and their analysis indicates that the new structure outperforms the traditional one.
Many load balancing problems that arise in scientific computing applications ask to partition a graph with weights on the vertices and costs on the edges into a given number of almost equally-weighted parts such that the maximum boundary cost over all parts is small. Here, this partitioning problem is considered for bounded-degree graphs G=(V,E) with edge costs c: E->R+ that have a p-separator theorem for some p>1, i.e., any (arbitrarily weighted) subgraph of G can be separated into two parts of roughly the same weight by removing a vertex set S such that the edges incident to S in the subgraph have total cost at most proportional to (SUM_e c^p_e)^(1/p), where the sum is over all edges e in the subgraph. We show for all positive integers k and weights w that the vertices of G can be partitioned into k parts such that the weight of each part differs from the average weight by less than MAX{w_v; v in V}, and the boundary edges of each part have cost at most proportional to (SUM_e c_e^p/k)^(1/p) + MAX_e c_e. The partition can be computed in time nearly proportional to the time for computing a separator S of G. Our upper bound on the boundary costs is shown to be tight up to a constant factor for infinitely many instances with a broad range of parameters. Previous results achieved this bound only if one has c=1, w=1, and one allows parts with weight exceeding the average by a constant fraction.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
