اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدOn Continuity Properties for Infinite Rectangle Packing
59
0
0.0
(
0
)
تأليف
Zhiheng Liu
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
By rectangle packing we mean putting a set of rectangles into an enclosing rectangle, without any overlapping. We begin with perfect rectangle packing problems, then prove two continuity properties for parallel rectangle packing problems, and discuss how they might be used to obtain negative results for perfect rectangle packing problems.
قيم البحث
اقرأ أيضاً
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.
The walk distances in graphs are defined as the result of appropriate transformations of the $sum_{k=0}^infty(tA)^k$ proximity measures, where $A$ is the weighted adjacency matrix of a connected weighted graph and $t$ is a sufficiently small positive
parameter. The walk distances are graph-geodetic, moreover, they converge to the shortest path distance and to the so-called long walk distance as the parameter $t$ approaches its limiting values. In this paper, simple expressions for the long walk distance are obtained. They involve the generalized inverse, minors, and inverses of submatrices of the symmetric irreducible singular M-matrix ${cal L}=rho I-A,$ where $rho$ is the Perron root of $A.$
For positive integers $ngeq kgeq t$, a collection $ mathcal{B} $ of $k$-subsets of an $n$-set $ X $ is called a $t$-packing if every $t$-subset of $ X $ appears in at most one set in $mathcal{B}$. In this paper, we give some upper and lower bounds fo
r the maximum size of $3$-packings when $n$ is sufficiently larger than $k$. In one case, the upper and lower bounds are equal, in some cases, they differ by at most an additive constant depending only on $k$ and in one case they differ by a linear bound in $ n $.
This paper proves a corner occupying theorem for the two-dimensional integral rectangle packing problem, stating that if it is possible to orthogonally place n arbitrarily given integral rectangles into an integral rectangular container without overl
apping, then we can achieve a feasible packing by successively placing an integral rectangle onto a bottom-left corner in the container. Based on this theorem, we might develop efficient heuristic algorithms for solving the integral rectangle packing problem. In fact, as a vague conjecture, this theorem has been implicitly mentioned with different appearances by many people for a long time.
Let $G$ be a graph of order $n(G)$ and vertex set $V(G)$. Given a set $Ssubseteq V(G)$, we define the external neighbourhood of $S$ as the set $N_e(S)$ of all vertices in $V(G)setminus S$ having at least one neighbour in $S$. The differential of $S$
is defined to be $partial(S)=|N_e(S)|-|S|$. In this paper, we introduce the study of the $2$-packing differential of a graph, which we define as $partial_{2p}(G)=max{partial(S): Ssubseteq V(G) text{ is a }2text{-packing}}.$ We show that the $2$-packing differential is closely related to several graph parameters, including the packing number, the independent domination number, the total domination number, the perfect differential, and the unique response Roman domination number. In particular, we show that the theory of $2$-packing differentials is an appropriate framework to investigate the unique response Roman domination number of a graph without the use of functions. Among other results, we obtain a Gallai-type theorem, which states that $partial_{2p}(G)+mu_{_R}(G)=n(G)$, where $mu_{_R}(G)$ denotes the unique response Roman domination number of $G$. As a consequence of the study, we derive several combinatorial results on $mu_{_R}(G)$, and we show that the problem of finding this parameter is NP-hard. In addition, the particular case of lexicographic product graphs is discussed.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
