Jug measuring: Algorithms and complexity

Min-Zheng Shieh, Shi-Chun Tsai*

*Corresponding author for this work

Research output: Contribution to journalArticle

1 Scopus citations

Abstract

We study the hardness of the optimal jug measuring problem. By proving tight lower and upper bounds on the minimum number of measuring steps required, we reduce an inapproximable NP-hard problem (i.e., the shortest GCD multiplier problem [G. Havas, J.-P. Seifert, The Complexity of the Extended GCD Problem, in: LNCS, vol. 1672, Springer, 1999]) to it. It follows that the optimal jug measuring problem is NP-hard and so is the problem of approximating the minimum number of measuring steps within a constant factor. Along the way, we give a polynomial-time approximation algorithm with an exponential error based on the well-known LLL basis reduction algorithm.

Original languageEnglish
Pages (from-to)50-62
Number of pages13
JournalTheoretical Computer Science
Volume396
Issue number1-3
DOIs
StatePublished - 10 May 2008

Keywords

  • Inapproximability
  • Jug measuring problem
  • Lattice problem
  • LLL algorithm

Fingerprint Dive into the research topics of 'Jug measuring: Algorithms and complexity'. Together they form a unique fingerprint.

Cite this