Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userCorner Occupying Theorem for the Two-dimensional Integral Rectangle Packing Problem
107
0
0.0
(
0
)
Added by
Tao Ye
Publication date
2011
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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 structural 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 coincides 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 anisotropic. 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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
