標題: 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
顯示於類別:期刊論文


文件中的檔案:

  1. 000256199100005.pdf

若為 zip 檔案,請下載檔案解壓縮後,用瀏覽器開啟資料夾中的 index.html 瀏覽全文。