Tommy Jensen

Batched Bin Packing

  • Gregory Gutin
  • Anders Yeo
  • Tommy Jensen
    • Categories Approximation Algorithms, Combinatorial Optimization Tags , , ,

    We introduce and study the batched bin packing problem (BBPP), a bin packing problem in which items become available for packing incrementally, one batch at a time. A batched algorithm must pack a batch before the next batch becomes known. A batch may contain several items; the special case when each batch consists of merely … Read more

    Domination analysis for minimum multiprocessor scheduling

  • Gregory Gutin
  • Anders Yeo
  • Tommy Jensen
    • Categories Approximation Algorithms Tags , ,

    Let $P$ be a combinatorial optimization problem, and let $A$ be an approximation algorithm for $P$. The domination ratio $\domr(A,s)$ is the maximal real $q$ such that the solution $x(I)$ obtained by $A$ for any instance $I$ of $P$ of size $s$ is not worse than at least the fraction $q$ of the feasible solutions … Read more