A (5/3+ε)-approximation for strip packing Harren, Rolf; Jansen, Klaus; Prädel, Lars ...
Computational geometry : theory and applications,
02/2014, Volume:
47, Issue:
2
Journal Article
Peer reviewed
Open access
We study strip packing, which is one of the most classical two-dimensional packing problems: given a collection of rectangles, the problem is to find a feasible orthogonal packing without rotations ...into a strip of width 1 and minimum height. In this paper we present an approximation algorithm for the strip packing problem with absolute approximation ratio of 5/3+ε for any ε>0. This result significantly narrows the gap between the best known upper bound and the lower bound of 3/2; previously, the best upper bound was 1.9396 due to Harren and van Stee.
We consider the problem of packing rectangles into bins that are unit squares, where the goal is to minimize the number of bins used. All rectangles have to be packed non-overlapping and orthogonal, ...i.e., axis-parallel. We present an algorithm with an absolute worst-case ratio of 2 for the case where the rectangles can be rotated by 90 degrees. This is optimal provided
. For the case where rotation is not allowed, we prove an approximation ratio of 3 for the algorithm
Hybrid First Fit
which was introduced by Chung et al. (SIAM J. Algebr. Discrete Methods 3(1):66–76,
1982
) and whose running time is slightly better than the running time of Zhang’s previously known 3-approximation algorithm (Zhang in Oper. Res. Lett. 33(2):121–126,
2005
).
We consider a memory allocation problem. This problem can be modeled as a version of bin packing where items may be split, but each bin may contain at most two (parts of) items. This problem was ...recently introduced by Chung et al. (Theory Comput. Syst. 39(6):829–849,
2006
). We give a simple
-approximation algorithm for this problem which is in fact an online algorithm. This algorithm also has good performance for the more general case where each bin may contain at most
k
parts of items. We show that this general case is strongly NP-hard for any
k
≥3. Additionally, we design an efficient approximation algorithm, for which the approximation ratio can be made arbitrarily close to
.
The high latencies for access to background memory like hard disks or flash memory can be reduced by caching or hidden by prefetching. We consider the problem of scheduling the resulting I/Os when ...the available fast cache memory is limited and when we have real-time constraints where for each requested data block we are given a time interval during which this block needs to be in main memory. We give a near linear time algorithm for this problem which produces a feasible schedule whenever one exists. Another algorithm additionally minimizes I/Os and still runs in polynomial-time. For the online variant of the problem, we give a competitive algorithm that uses lookahead and augmented disk speed. We show a tight relationship between the amount of lookahead and the speed required to get a competitive algorithm.
Online Bin Stretching
is a semi-online variant of bin packing in which the algorithm has to use the same number of bins as an optimal packing, but is allowed to slightly overpack the bins. The goal ...is to minimize the amount of overpacking, i.e., the maximum size packed into any bin.We give an algorithm for
Online Bin Stretching
with a stretching factor of 1.5 for any number of bins. We build on previous algorithms and use a two-phase approach. However, our analysis is technically more complicated and uses amortization over the bins with the help of two weight functions.
Online bin stretching with three bins Böhm, Martin; Sgall, Jiří; van Stee, Rob ...
Journal of scheduling,
12/2017, Volume:
20, Issue:
6
Journal Article
Peer reviewed
Open access
Online bin stretching is a semi-online variant of bin packing in which the algorithm has to use the same number of bins as an optimal packing, but is allowed to slightly overpack the bins. The goal ...is to minimize the amount of overpacking, i.e., the maximum size packed into any bin. We give an algorithm for online bin stretching with a stretching factor of
11
/
8
=
1.375
for three bins. Additionally, we present a lower bound of
45
/
33
=
1
.
36
¯
for online bin stretching on three bins and a lower bound of 19/14 for four and five bins that were discovered using a computer search.
We continue the study of the online unit clustering problem, introduced by Chan and Zarrabi-Zadeh (
Workshop on Approximation and Online Algorithms 2006
, LNCS 4368, p. 121--131. Springer, 2006). We ...design a deterministic algorithm with a competitive ratio of 7/4 for the one-dimensional case. This is the first deterministic algorithm that beats the bound of 2. It also has a better competitive ratio than the previous randomized algorithms. Moreover, we provide the first non-trivial deterministic lower bound, improve the randomized lower bound, and prove the first lower bounds for higher dimensions.
In the cake cutting problem, a cake needs to be divided among players with possibly different valuations for different pieces of the cake. We consider a variation where the cake represents chores ...that need to be allocated. We assume the players to be work-averse, i.e., intending to get as little of the cake as possible. We further assume that the chores are indivisible and that they are ordered along a line. We seek a fair allocation of the chores.
We study the loss in social welfare due to fairness using the price of fairness concept. Previous work has considered fair division of cakes and chores with non-connected and connected pieces as well as fair division of indivisible contiguous blocks of indivisible items (with positive utility) on a line. We complete the picture by providing price of fairness results for the allocation of contiguous blocks of indivisible chores.
Dividing connected chores fairly Heydrich, Sandy; van Stee, Rob
Theoretical computer science,
08/2015, Volume:
593
Journal Article
Peer reviewed
Open access
In this paper we consider the fair division of chores (tasks that need to be performed by agents, with negative utility for them), and study the loss in social welfare due to fairness. Previous work ...has been done on this so-called price of fairness, concerning fair division of cakes and chores with non-connected pieces and of cakes with connected pieces. In this paper, we consider situations where each player has to receive one connected piece of the chores. We provide tight or nearly tight bounds on the price of fairness with respect to the three main fairness criteria proportionality, envy-freeness and equitability and for utilitarian and egalitarian welfare. We also give the first proof of the existence of equitable divisions for chores with connected pieces.
•New model for the buffer minimization with conflicts problem; Load arrives continuously.•Tight bounds on the competitive ratio for paths of various lengths.•Improved lower bound for the original ...model.•Algorithm for machines with speed augmentation.
In the buffer minimization in multiprocessor systems with conflicts or simply buffer minimization problem, a multi-processor system is modelled as an undirected graph. A conflict occurs if two processors are connected by an edge. Conflicting processors can not run at the same time. At any time, load may arrive on one or more processors. Incoming workload is stored in an input buffer and a machine that is running reduces its workload at a constant rate. The goal is to find a schedule that minimizes the maximum workload over all machines and over time. We consider the special case where the graph is a path. We give upper and lower bounds on the competitive ratio for paths of various lengths. We also consider online algorithms that have resource augmentation on their speed (processing rate), and give a (1+2ε)-speed (1/ε+2)-competitive algorithm.
PDF
