Improved Bound on Approximating Jug Measuring Problem

dc.citation.epage	1163	en_US
dc.citation.issue	3	en_US
dc.citation.spage	1159	en_US
dc.citation.volume	27	en_US
dc.citation.woscount	0
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:11:36Z
dc.date.available	2014-12-08T15:11:36Z
dc.date.issued	2011-05-01	en_US
dc.description.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.	en_US
dc.identifier.issn	1016-2364	en_US
dc.identifier.journal	JOURNAL OF INFORMATION SCIENCE AND ENGINEERING	en_US
dc.identifier.uri	https://ir.lib.nycu.edu.tw/handle/11536/8904
dc.identifier.wosnumber	WOS:000291237900023
dc.language.iso	en_US	en_US
dc.subject	jug measuring problem	en_US
dc.subject	approximation	en_US
dc.subject	NP-hardness	en_US
dc.subject	inapproximability	en_US
dc.subject	shortest integer solution	en_US
dc.title	Improved Bound on Approximating Jug Measuring Problem	en_US
dc.type	Article	en_US

Files

Now showing 1 - 1 of 1