Improved Bound on Approximating Jug Measuring Problem

Abstract

In this note, we investigate the hardness of approximating the optimal jug measuring problem, which studies how to use jugs with certain capacities to measure a given quantity in minimum steps. Based on a recent related development, we prove that it is NP-hard to approximate this problem within n(c/loglog n) for some constant c > 0. This improves previous known result significantly.