Jug measuring: Algorithms and complexity
| dc.citation.epage | 62 | en_US |
| dc.citation.issue | 1-3 | en_US |
| dc.citation.spage | 50 | en_US |
| dc.citation.volume | 396 | en_US |
| dc.citation.woscount | 1 | |
| dc.contributor.author | Shieh, Min-Zheng | en_US |
| dc.contributor.author | Tsai, Shi-Chun | en_US |
| dc.contributor.department | 資訊工程學系 | zh_TW |
| dc.contributor.department | Department of Computer Science | en_US |
| dc.date.accessioned | 2014-12-08T15:12:10Z | |
| dc.date.available | 2014-12-08T15:12:10Z | |
| dc.date.issued | 2008-05-10 | en_US |
| dc.description.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. (C) 2008 Elsevier B.V. All rights reserved. | en_US |
| dc.identifier.doi | 10.1016/j.tcs.2008.01.003 | en_US |
| dc.identifier.issn | 0304-3975 | en_US |
| dc.identifier.journal | THEORETICAL COMPUTER SCIENCE | en_US |
| dc.identifier.uri | http://dx.doi.org/10.1016/j.tcs.2008.01.003 | en_US |
| dc.identifier.uri | https://ir.lib.nycu.edu.tw/handle/11536/9338 | |
| dc.identifier.wosnumber | WOS:000256199100005 | |
| dc.language.iso | en_US | en_US |
| dc.subject | Jug measuring problem | en_US |
| dc.subject | inapproximability | en_US |
| dc.subject | LLL algorithm | en_US |
| dc.subject | lattice problem | en_US |
| dc.title | Jug measuring: Algorithms and complexity | en_US |
| dc.type | Article | en_US |