Previous [ 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 (May 2011)

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

Full Text (¥þ¤åÀÉ) Retrieve PDF document (201105_22.pdf)

Received September 10, 2009; revised January 12, 2010; accepted January 19, 2010.
Communicated by Chi-Jen Lu.
1 For the definitions of complexity classes we refer to standard textbook, such as Sipser¡¦s [4].
2 SDESP is called minimum solutions of linear Diophantine equations (MSD) in [7].