Resumen The integer equal flow problem is an NP-hard network flow problem, in which all arcs in given sets R1,…,Rl must carry equal flow. We show that this problem is effectively inapproximable, even if the cardinality of each set Rk is two. When l is fixed, it is solvable in polynomial time.
Resumen
We consider the scheduling problem of minimizing the average-weighted completion time on identical parallel machines when jobs are arriving over time. For both the preemptive and the nonpreemptive setting, we show that straightforward extensions of Smith's ratio rule yield smaller competitive ratios than the previously best-known deterministic on-line algorithms.
