Improved Bound on Approximating Jug Measuring Problem

完整後設資料紀錄

DC 欄位	值	語言
dc.contributor.author	Shieh, Min-Zheng	en_US
dc.contributor.author	Tsai, Shi-Chun	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.identifier.issn	1016-2364	en_US
dc.identifier.uri	http://hdl.handle.net/11536/8904	-
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.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
dc.identifier.journal	JOURNAL OF INFORMATION SCIENCE AND ENGINEERING	en_US
dc.citation.volume	27	en_US
dc.citation.issue	3	en_US
dc.citation.spage	1159	en_US
dc.citation.epage	1163	en_US
dc.contributor.department	資訊工程學系	zh_TW
dc.contributor.department	Department of Computer Science	en_US
dc.identifier.wosnumber	WOS:000291237900023	-
dc.citation.woscount	0	-
顯示於類別：	期刊論文