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.
|Number of pages||5|
|Journal||Journal of Information Science and Engineering|
|State||Published - 1 May 2011|
- Jug measuring problem
- Shortest integer solution