完整後設資料紀錄
DC 欄位語言
dc.contributor.authorShieh, Min-Zhengen_US
dc.contributor.authorTsai, Shi-Chunen_US
dc.date.accessioned2014-12-08T15:12:10Z-
dc.date.available2014-12-08T15:12:10Z-
dc.date.issued2008-05-10en_US
dc.identifier.issn0304-3975en_US
dc.identifier.urihttp://dx.doi.org/10.1016/j.tcs.2008.01.003en_US
dc.identifier.urihttp://hdl.handle.net/11536/9338-
dc.description.abstractWe 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.language.isoen_USen_US
dc.subjectJug measuring problemen_US
dc.subjectinapproximabilityen_US
dc.subjectLLL algorithmen_US
dc.subjectlattice problemen_US
dc.titleJug measuring: Algorithms and complexityen_US
dc.typeArticleen_US
dc.identifier.doi10.1016/j.tcs.2008.01.003en_US
dc.identifier.journalTHEORETICAL COMPUTER SCIENCEen_US
dc.citation.volume396en_US
dc.citation.issue1-3en_US
dc.citation.spage50en_US
dc.citation.epage62en_US
dc.contributor.department資訊工程學系zh_TW
dc.contributor.departmentDepartment of Computer Scienceen_US
dc.identifier.wosnumberWOS:000256199100005-
dc.citation.woscount1-
顯示於類別:期刊論文


文件中的檔案:

  1. 000256199100005.pdf

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