Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userNear Linear Time Approximation Schemes for Uncapacitated and Capacitated b--Matching Problems in Nonbipartite Graphs
227
0
0.0
(
0
)
Added by
Sudipto Guha
Publication date
2013
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We present the first near optimal approximation schemes for the maximum weighted (uncapacitated or capacitated) $b$--matching problems for non-bipartite graphs that run in time (near) linear in the number of edges. For any $delta>3/sqrt{n}$ the algorithm produces a $(1-delta)$ approximation in $O(m poly(delta^{-1},log n))$ time. We provide fractional solutions for the standard linear programming formulations for these problems and subsequently also provide (near) linear time approximation schemes for rounding the fractional solutions. Through these problems as a vehicle, we also present several ideas in the context of solving linear programs approximately using fast primal-dual algorithms. First, even though the dual of these problems have exponentially many variables and an efficient exact computation of dual weights is infeasible, we show that we can efficiently compute and use a sparse approximation of the dual weights using a combination of (i) adding perturbation to the constraints of the polytope and (ii) amplification followed by thresholding of the dual weights. Second, we show that approximation algorithms can be used to reduce the width of the formulation, and faster convergence.
rate research
Read More
We give an asymptotic approximation scheme (APTAS) for the problem of packing a set of circles into a minimum number of unit square bins. To obtain rational solutions, we use augmented bins of height $1+gamma$, for some arbitrarily small number $gamma > 0$. Our algorithm is polynomial on $log 1/gamma$, and thus $gamma$ is part of the problem input. For the special case that $gamma$ is constant, we give a (one dimensional) resource augmentation scheme, that is, we obtain a packing into bins of unit width and height $1+gamma$ using no more than the number of bins in an optimal packing. Additionally, we obtain an APTAS for the circle strip packing problem, whose goal is to pack a set of circles into a strip of unit width and minimum height. These are the first approximation and resource augmentation schemes for these problems. Our algorithm is based on novel ideas of iteratively separating small and large items, and may be extended to a wide range of packing problems that satisfy certain conditions. These extensions comprise problems with different kinds of items, such as regular polygons, or with bins of different shapes, such as circles and spheres. As an example, we obtain APTASs for the problems of packing d-dimensional spheres into hypercubes under the $L_p$-norm.
Retraction note: After posting the manuscript on arXiv, we were informed by Erik Jan van Leeuwen that both results were known and they appeared in his thesis[vL09]. A PTAS for MDS is at Theorem 6.3.21 on page 79 and A PTAS for MCDS is at Theorem 6.3.31 on page 82. The techniques used are very similar. He noted that the idea for dealing with the connected version using a constant number of extra layers in the shifting technique not only appeared Zhang et al.[ZGWD09] but also in his 2005 paper [vL05]. Finally, van Leeuwen also informed us that the open problem that we posted has been resolved by Marx~[Mar06, Mar07] who showed that an efficient PTAS for MDS does not exist [Mar06] and under ETH, the running time of $n^{O(1/epsilon)}$ is best possible [Mar07]. We thank Erik Jan van Leeuwen for the information and we regret that we made this mistake. Abstract before retraction: We present two (exponentially) faster PTASs for dominating set problems in unit disk graphs. Given a geometric representation of a unit disk graph, our PTASs that find $(1+epsilon)$-approximate solutions to the Minimum Dominating Set (MDS) and the Minimum Connected Dominating Set (MCDS) of the input graph run in time $n^{O(1/epsilon)}$. This can be compared to the best known $n^{O(1/epsilon log {1/epsilon})}$-time PTAS by Nieberg and Hurink~[WAOA05] for MDS that only uses graph structures and an $n^{O(1/epsilon^2)}$-time PTAS for MCDS by Zhang, Gao, Wu, and Du~[J Glob Optim09]. Our key ingredients are improved dynamic programming algorithms that depend exponentially on more essential 1-dimensional widths of the problems.
We give polynomial-time approximation schemes for monotone maximization problems expressible in terms of distances (up to a fixed upper bound) and efficiently solvable in graphs of bounded treewidth. These schemes apply in all fractionally treewidth-fragile graph classes, a property that is true for many natural graph classes with sublinear separators. We also provide quasipolynomial-time approximation schemes for these problems in all classes with sublinear separators.
The $k$-Facility Location problem is a generalization of the classical problems $k$-Median and Facility Location. The goal is to select a subset of at most $k$ facilities that minimizes the total cost of opened facilities and established connections between clients and opened facilities. We consider the hard-capacitated version of the problem, where a single facility may only serve a limited number of clients and creating multiple copies of a facility is not allowed. We construct approximation algorithms slightly violating the capacities based on rounding a fractional solution to the standard LP. It is well known that the standard LP (even in the case of uniform capacities and opening costs) has unbounded integrality gap if we only allow violating capacities by a factor smaller than $2$, or if we only allow violating the number of facilities by a factor smaller than $2$. In this paper, we present the first constant-factor approximation algorithms for the hard-capacitated variants of the problem. For uniform capacities, we obtain a $(2+varepsilon)$-capacity violating algorithm with approximation ratio $O(1/varepsilon^2)$; our result has not yet been improved. Then, for non-uniform capacities, we consider the case of $k$-Median, which is equivalent to $k$-Facility Location with uniform opening cost of the facilities. Here, we obtain a $(3+varepsilon)$-capacity violating algorithm with approximation ratio $O(1/varepsilon)$.
We provide a randomized linear time approximation scheme for a generic problem about clustering of binary vectors subject to additional constrains. The new constrained clustering problem encompasses a number of problems and by solving it, we obtain the first linear time-approximation schemes for a number of well-studied fundamental problems concerning clustering of binary vectors and low-rank approximation of binary matrices. Among the problems solvable by our approach are textsc{Low GF(2)-Rank Approximation}, textsc{Low Boolean-Rank Approximation}, and vario
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
