Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userPolynomial-Time Approximation Schemes for Circle and Other Packing Problems
169
0
0.0
(
0
)
Added by
Lehilton Pedrosa
Publication date
2014
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
The question of whether all problems in NP class are also in P class is generally considered one of the most important open questions in mathematics and theoretical computer science as it has far-reaching consequences to other problems in mathematics, computer science, biology, philosophy and cryptography. There are intensive research on proving `NP not equal to P and `NP equals to P. However, none of the `proved results is commonly accepted by the research community up to date. In this paper, motived by approximability of traveling salesman problem (TSP) in polynomial time, we aim to provide a new perspective: showing that NP=P from polynomial time approximation-bounded solutions of TSP in Euclidean space.
We consider the online problem of packing circles into a square container. A sequence of circles has to be packed one at a time, without knowledge of the following incoming circles and without moving previously packed circles. We present an algorithm that packs any online sequence of circles with a combined area not larger than 0.350389 0.350389 of the squares area, improving the previous best value of {pi}/10 approx 0.31416; even in an offline setting, there is an upper bound of {pi}/(3 + 2 sqrt{2}) approx 0.5390. If only circles with radii of at least 0.026622 are considered, our algorithm achieves the higher value 0.375898. As a byproduct, we give an online algorithm for packing circles into a 1times b rectangle with b geq 1. This algorithm is worst case-optimal for b geq 2.36.
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
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.
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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
