اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدCorner Occupying Theorem for the Two-dimensional Integral Rectangle Packing Problem
109
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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 overlapping, 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 an $n$-node graph without two disjoint odd cycles. The algorithm of Artmann, Weismantel and Zenklusen (STOC17) for bimodular integer programs can be used to find a maximum weight stable set in $G$ in strongly polynomial time. Building on s
tructural results characterizing sufficiently connected graphs without two disjoint odd cycles, we construct a size-$O(n^2)$ extended formulation for the stable set polytope of $G$.
Let $P_{n}$ be a set of $n$ points, including the origin, in the unit square $U = [0,1]^2$. We consider the problem of constructing $n$ axis-parallel and mutually disjoint rectangles inside $U$ such that the bottom-left corner of each rectangle coinc
ides with a point in $P_{n}$ and the total area covered by the rectangles is maximized cite{ibmpuzzle}, cite{Winkler2007}, cite{Winkler2010a}, cite{Winkler2010b}. The longstanding conjecture has been that at least half of $U$ can be covered when such rectangles are properly placed. In this paper, we give an existential proof of the conjecture.
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.
We give four new proofs of the directed version of Brooks Theorem and an NP-completeness result.
Two-dimensional electrons in AlAs quantum wells occupy multiple conduction-band minima at the X- points of the Brillouin zone. These valleys have large effective mass and g-factor compared to the stan-dard GaAs electrons, and are also highly anisotro
pic. With proper choice of well width and by applying symmetry-breaking strain in the plane, one can control the occupation of different valleys thus rendering a system with tuneable effective mass, g-factor, Fermi contour anisotropy, and valley degeneracy. Here we review some of the rich physics that this system has allowed us to explore.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
