Improved approximation bounds via problem independent LP modeling: application to Incremental Knapsack Problem and to Parallel-Machine Load Balancing Problem

Longest Processing Time rule for identical parallel machines revisited (F. Della Croce, R. Scatamacchia)
We consider problem P || Cmax  where the goal is to schedule n jobs on m identical parallel machines in order to minimize the makespan.
For this NP-hard problem, we revisit the famous Longest Processing Time (LPT) rule proposed by Graham in 1969.
LPT rule requires to sort the jobs in non-ascending order of their processing times and then to assign one job at a time
to the machine whose load is smallest so far. The contribution of our work is twofold.
First, we provide new insights on LPT properties and a discuss the worst case performance of a slight modification of LPT
that manages to improve the longstanding Graham's bound from (4/3 - 1/(3m) ) to (4/3 - 1/(3(m-1)) for m>=3 and from 7/6 to 9/8 for m=2.
We employ Linear Programming (LP) to analyze the worst case performance of our approaches.
Then, we move from approximation to heuristics. By generalizing the proposed LPT revisiting, we obtain a simple O(n log n) heuristic that drastically improves upon the performance of LPT.
The heuristic splits the sorted job set in tuples of m consecutive jobs (1,...,m; m+1,...,2m; etc.)
and sorts the tuples in non-increasing order of the difference (slack) between the largest job and the smallest job in the tuple. Then, List Scheduling is applied to the set of sorted tuples. This approach turns out to strongly outperforms LPT
on a large set of benchmark literature instances.


Approximation results for the Incremental Knapsack problem (F. Della Croce, U. Pferschy, R. Scatamacchia)
We consider the 0/1 Incremental Knapsack Problem (IKP) where the capacity grows over time periods and if an item is placed in the knapsack in a certain period, it cannot be removed afterwards. The problem calls for maximizing the sum of the prots over the whole time horizon. In this work, we provide approximation results for IKP and its restricted variants.
Interestingly, we also rely on Linear Programming (LP) for deriving approximation bounds and show how the proposed
LP-based analysis can be seen as a valid alternative to more formal proof systems. We first manage to prove the tightness
of some approximation ratios of a general purpose algorithm currently available in the literature.
We also devise a Polynomial Time Approximation Scheme (PTAS) when the input value indicating the number of periods
is considered as a constant. Then, we add the mild and natural assumption that each item can be packed in the first time period.
For this variant, we discuss different approximation algorithms suited for any number of time periods and provide algorithms
with a constant approximation factor of 6/7 for the case with two periods and of 30/37 for the variant with three periods.