標題: | Jug measuring: Algorithms and complexity |
作者: | Shieh, Min-Zheng Tsai, Shi-Chun 資訊工程學系 Department of Computer Science |
關鍵字: | Jug measuring problem;inapproximability;LLL algorithm;lattice problem |
公開日期: | 10-五月-2008 |
摘要: | 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. (C) 2008 Elsevier B.V. All rights reserved. |
URI: | http://dx.doi.org/10.1016/j.tcs.2008.01.003 http://hdl.handle.net/11536/9338 |
ISSN: | 0304-3975 |
DOI: | 10.1016/j.tcs.2008.01.003 |
期刊: | THEORETICAL COMPUTER SCIENCE |
Volume: | 396 |
Issue: | 1-3 |
起始頁: | 50 |
結束頁: | 62 |
顯示於類別: | 期刊論文 |