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] |

¡@

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 (**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].