JISE

[1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24]

Journal of Information Science and Engineering, Vol. 27 No. 3, pp. 1159-1163

Improved Bound on Approximating Jug Measuring Problem

MIN-ZHENG SHIEH AND SHI-CHUN TSAI
Department of Computer Science
National Chiao Tung University
Hsinchu, 300 Taiwan

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 nc/loglog n for some constant c > 0. This improves previous known result significantly.

Keywords: jug measuring problem, approximation, NP-hardness, inapproximability, shortest integer solution

Retrieve PDF document (JISE_201103_23.pdf)