Improved bound on approximating jug measuring problem

Min-Zheng Shieh*, Shi-Chun Tsai

*Corresponding author for this work

Research output: Contribution to journalArticle

Abstract

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.

Original languageEnglish
Pages (from-to)1159-1163
Number of pages5
JournalJournal of Information Science and Engineering
Volume27
Issue number3
StatePublished - 1 May 2011

Keywords

  • Approximation
  • Inapproximability
  • Jug measuring problem
  • NP-hardness
  • Shortest integer solution

Fingerprint Dive into the research topics of 'Improved bound on approximating jug measuring problem'. Together they form a unique fingerprint.

  • Cite this