Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA tight lower bound for the online bounded space hypercube bin packing problem
77
0
0.0
(
0
)
Added by
Yoshiharu Kohayakawa
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
In the $d$-dimensional hypercube bin packing problem, a given list of $d$-dimensional hypercubes must be packed into the smallest number of hypercube bins. Epstein and van Stee [SIAM J. Comput. 35 (2005)] showed that the asymptotic performance ratio $rho$ of the online bounded space variant is $Omega(log d)$ and $O(d/log d)$, and conjectured that it is $Theta(log d)$. We show that $rho$ is in fact $Theta(d/log d)$, using probabilistic arguments.
rate research
Read More
We prove a tight lower bound on the asymptotic performance ratio $rho$ of the bounded space online $d$-hypercube bin packing problem, solving an open question raised in 2005. In the classic $d$-hypercube bin packing problem, we are given a sequence of $d$-dimensional hypercubes and we have an unlimited number of bins, each of which is a $d$-dimensional unit hypercube. The goal is to pack (orthogonally) the given hypercubes into the minimum possible number of bins, in such a way that no two hypercubes in the same bin overlap. The bounded space online $d$-hypercube bin packing problem is a variant of the $d$-hypercube bin packing problem, in which the hypercubes arrive online and each one must be packed in an open bin without the knowledge of the next hypercubes. Moreover, at each moment, only a constant number of open bins are allowed (whenever a new bin is used, it is considered open, and it remains so until it is considered closed, in which case, it is not allowed to accept new hypercubes). Epstein and van Stee [SIAM J. Comput. 35 (2005), no. 2, 431-448] showed that $rho$ is $Omega(log d)$ and $O(d/log d)$, and conjectured that it is $Theta(log d)$. We show that $rho$ is in fact $Theta(d/log d)$. To obtain this result, we elaborate on some ideas presented by those authors, and go one step further showing how to obtain better (offline) packings of certain special instances for which one knows how many bins any bounded space algorithm has to use. Our main contribution establishes the existence of such packings, for large enough $d$, using probabilistic arguments. Such packings also lead to lower bounds for the prices of anarchy of the selfish $d$-hypercube bin packing game. We present a lower bound of $Omega(d/log d)$ for the pure price of anarchy of this game, and we also give a lower bound of $Omega(log d)$ for its strong price of anarchy.
We study emph{parallel} online algorithms: For some fixed integer $k$, a collective of $k$ parallel processes that perform online decisions on the same sequence of events forms a $k$-emph{copy algorithm}. For any given time and input sequence, the overall performance is determined by the best of the $k$ individual total results. Problems of this type have been considered for online makespan minimization; they are also related to optimization with emph{advice} on future events, i.e., a number of bits available in advance. We develop textsc{Predictive Harmonic}$_3$ (PH3), a relatively simple family of $k$-copy algorithms for the online Bin Packing Problem, whose joint competitive factor converges to 1.5 for increasing $k$. In particular, we show that $k=6$ suffices to guarantee a factor of $1.5714$ for PH3, which is better than $1.57829$, the performance of the best known 1-copy algorithm textsc{Advanced Harmonic}, while $k=11$ suffices to achieve a factor of $1.5406$, beating the known lower bound of $1.54278$ for a single online algorithm. In the context of online optimization with advice, our approach implies that 4 bits suffice to achieve a factor better than this bound of $1.54278$, which is considerably less than the previous bound of 15 bits.
We consider the file maintenance problem (also called the online labeling problem) in which n integer items from the set {1,...,r} are to be stored in an array of size m >= n. The items are presented sequentially in an arbitrary order, and must be stored in the array in sorted order (but not necessarily in consecutive locations in the array). Each new item must be stored in the array before the next item is received. If r<=m then we can simply store item j in location j but if r>m then we may have to shift the location of stored items to make space for a newly arrived item. The algorithm is charged each time an item is stored in the array, or moved to a new location. The goal is to minimize the total number of such moves done by the algorithm. This problem is non-trivial when n=<m<r. In the case that m=Cn for some C>1, algorithms for this problem with cost O(log(n)^2) per item have been given [IKR81, Wil92, BCD+02]. When m=n, algorithms with cost O(log(n)^3) per item were given [Zha93, BS07]. In this paper we prove lower bounds that show that these algorithms are optimal, up to constant factors. Previously, the only lower bound known for this range of parameters was a lower bound of Omega(log(n)^2) for the restricted class of smooth algorithms [DSZ05a, Zha93]. We also provide an algorithm for the sparse case: If the number of items is polylogarithmic in the array size then the problem can be solved in amortized constant time per item.
We give the first $2$-approximation algorithm for the cluster vertex deletion problem. This is tight, since approximating the problem within any constant factor smaller than $2$ is UGC-hard. Our algorithm combines the previous approaches, based on the local ratio technique and the management of true twins, with a novel construction of a good cost function on the vertices at distance at most $2$ from any vertex of the input graph. As an additional contribution, we also study cluster vertex deletion from the polyhedral perspective, where we prove almost matching upper and lower bounds on how well linear programming relaxations can approximate the problem.
We prove that with high probability over the choice of a random graph $G$ from the ErdH{o}s-Renyi distribution $G(n,1/2)$, the $n^{O(d)}$-time degree $d$ Sum-of-Squares semidefinite programming relaxation for the clique problem will give a value of at least $n^{1/2-c(d/log n)^{1/2}}$ for some constant $c>0$. This yields a nearly tight $n^{1/2 - o(1)}$ bound on the value of this program for any degree $d = o(log n)$. Moreover we introduce a new framework that we call emph{pseudo-calibration} to construct Sum of Squares lower bounds. This framework is inspired by taking a computational analog of Bayesian probability theory. It yields a general recipe for constructing good pseudo-distributions (i.e., dual certificates for the Sum-of-Squares semidefinite program), and sheds further light on the ways in which this hierarchy differs from others.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
