We study the strip packing problem, a classical packing problem which generalizes both bin packing and makespan minimization. Here we are given a set of axis-parallel rectangles in the two-dimensional plane and the goal is to pack them in a vertical strip of a fixed width such that the height of the obtained packing is minimized. The packing must be non-overlapping and the rectangles cannot be rotated. A reduction from the partition problem shows that no approximation better than 3 2 is possible for strip packing in polynomial time (assuming P @math NP). Nadiradze and Wiese [SODA16] overcame this barrier by presenting a @math -approximation algorithm in pseudo-polynomial-time (PPT). As the problem is strongly NP-hard, it does not admit an exact PPT algorithm. In this paper, we make further progress on the PPT approximability of strip packing, by presenting a @math -approximation algorithm. Our result is based on a non-trivial repacking of some rectangles in the left by the construction by Nadiradze and Wiese, and in some sense pushes their approach to its limit. Our PPT algorithm can be adapted to the case where we are allowed to rotate the rectangles by @math , achieving the same approximation factor and breaking the polynomial-time approximation barrier of 3 2 for the case with rotations as well.
 We consider the two-dimensional geometric knapsack problem defined as follows. Given a collection of rectangular axis-parallel items with weights, we want to find a maximum weight subset of the items that can be packed into a rectangular knapsack, i.e., which can be assigned positions within the knapsack such that the items are pairwise non-overlapping. The goal is to compute the optimal collection of items together with a feasible packing. The problem arises naturally in several applications, and various special cases of the problem have been studied. For the general case the best known result is a (2 + e)-approximation algorithm, while the only hardness result is NP-hardness. Our main result is a (1 + e)-approximation algorithm that runs in quasi-polynomial time, provided that the input data consists of (quasi-)polynomially bounded integers. We achieve this result in the setting with and without allowing rotation of the items. Our key technical contribution is to show the existence of a partition for the knapsack into a small number of rectangular boxes. Intuitively, this partition describes the segmentation of the knapsack in some near-optimal solution into large items, areas containing items that are high and thin, and areas containing items that are small and wide. Handling the interaction between these three types of items is a core bottleneck in the design of approximation algorithms for the problem and our partition allows to control this at only marginal cost. In particular, it is so powerful that we do not even need to round the sizes of the items, which is a canonical step in algorithms for geometric knapsack, geometric bin-packing, etc. Finally, we present new algorithms for two-dimensional knapsack and two-dimensional bin-packing under (1 + e)-resource augmentation with a substantially better running time dependence on e (although at the expense of requiring quasi-polynomial time). The objective value of our computed solutions is as good as the optimum without additional resources. Here we exploit a recent result showing the existence of certain low-complexity low weight separators for sets of non-overlapping rectangles.    We study the unsplittable flow on a path problem (UFP), which arises naturally in many applications such as bandwidth allocation, job scheduling, and caching. Here we are given a path with nonnegative edge capacities and a set of tasks, which are characterized by a subpath, a demand, and a profit. The goal is to find the most profitable subset of tasks whose total demand does not violate the edge capacities. Not surprisingly, this problem has received a lot of attention in the research community. If the demand of each task is at most a small enough fraction δ of the capacity along its subpath (δ-small tasks), then it has been known for a long time [, ICALP 2003] how to compute a solution of value arbitrarily close to the optimum via LP rounding. However, much remains unknown for the complementary case, that is, when the demand of each task is at least some fraction δ > 0 of the smallest capacity of its subpath (δ-large tasks). For this setting a constant factor approximation, improving on an earlier logarithmic approximation, was found only recently [, FOCS 2011]. In this paper we present a PTAS for δ-large tasks, for any constant δ > 0. Key to this result is a complex geometrically inspired dynamic program. Each task is represented as a segment underneath the capacity curve, and we identify a proper maze-like structure so that each corridor of the maze is crossed by only O(1) tasks in the optimal solution. The maze has a tree topology, which guides our dynamic program. Our result implies a 2 + e approximation for UFP, for any constant e > 0, improving on the previously best 7 + e approximation by We remark that our improved approximation algorithm matches the best known approximation ratio for the considerably easier special case of uniform edge capacities.  In the Maximum Weight Independent Set of Rectangles (MWISR) problem we are given a set of n axis-parallel rectangles in the 2D-plane, and the goal is to select a maximum weight subset of pairwise non-overlapping rectangles. Due to many applications, e.g. in data mining, map labeling and admission control, the problem has received a lot of attention by various research communities. We present the first (1 + e)-approximation algorithm for the MWISR problem with quasipolynomial running time 2poly(log n e). In contrast, the best known polynomial time approximation algorithms for the problem achieve superconstant approximation ratios of O(log log n) (unweighted case) and O(log n log log n) (weighted case). Key to our results is a new geometric dynamic program which recursively subdivides the plane into polygons of bounded complexity. We provide the technical tools that are needed to analyze its performance. In particular, we present a method of partitioning the plane into small and simple areas such that the rectangles of an optimal solution are intersected in a very controlled manner. Together with a novel application of the weighted planar graph separator theorem due to [4] this allows us to upper bound our approximation ratio by 1 + e. Our dynamic program is very general and we believe that it will be useful for other settings. In particular, we show that, when parametrized properly, it provides a polynomial time (1 + e)-approximation for the special case of the MWISR problem when each rectangle is relatively large in at least one dimension. Key to this analysis is a method to tile the plane in order to approximately describe the topology of these rectangles in an optimal solution. This technique might be a useful insight to design better polynomial time approximation algorithms or even a PTAS for the MWISR problem. In particular, note that our results imply that the MWISR problem is not APX-hard, unless NP ⊆ DTIME(2polylog (n)). We study the two-dimensional geometric knapsack problem (2DK) in which we are given a set of n axis-aligned rectangular items, each one with an associated profit, and an axis-aligned square knapsack. The goal is to find a (non-overlapping) packing of a maximum profit subset of items inside the knapsack (without rotating items). The best-known polynomial-time approximation factor for this problem (even just in the cardinality case) is (2 + ) [Jansen and Zhang, SODA 2004]. In this paper, we break the 2 approximation barrier, achieving a polynomial-time (17 9 + ) < 1.89 approximation, which improves to (558 325 + ) < 1.72 in the cardinality case. Essentially all prior work on 2DK approximation packs items inside a constant number of rectangular containers, where items inside each container are packed using a simple greedy strategy. We deviate for the first time from this setting: we show that there exists a large profit solution where items are packed inside a constant number of containers plus one L-shaped region at the boundary of the knapsack which contains items that are high and narrow and items that are wide and thin. As a second major and the main algorithmic contribution of this paper, we present a PTAS for this case. We believe that this will turn out to be useful in future work in geometric packing problems. We also consider the variant of the problem with rotations (2DKR), where items can be rotated by 90 degrees. Also, in this case, the best-known polynomial-time approximation factor (even for the cardinality case) is (2 + ) [Jansen and Zhang, SODA 2004]. Exploiting part of the machinery developed for 2DK plus a few additional ideas, we obtain a polynomial-time (3 2 + )-approximation for 2DKR, which improves to (4 3 + ) in the cardinality case.  We study the two-dimensional bin packing problem with and without rotations. Here we are given a set of two-dimensional rectangular items I and the goal is to pack these into a minimum number of unit square bins. We consider the orthogonal packing case where the edges of the items must be aligned parallel to the edges of the bin. Our main result is a 1.405-approximation for two-dimensional bin packing with and without rotation, which improves upon a recent 1.5 approximation due to Jansen and Pradel. We also show that a wide class of rounding based algorithms cannot improve upon the factor of 1.5. 