QQ客服 官方微博 反馈留言

	Breadth first greedy algorithm for unconstrained set multicover
	Cui, Peng ; Liu, Tian ; Qian, Liyan ; Zhou, Jin
	2007
关键词	breadth first greedy algorithm unconstrained set multicover approximation multiplicative weights update method INTEGER PROGRAMS
英文摘要	The simple greedy algorithm for unconstrained set multicover has approximation ratio Inn + 1. This paper presents a variation of the simple greedy algorithm, Breadth First Greedy Algorithm, and proves its approximation ratio can be (ln n)/r+ln ln n+O(1), where r is the cover requirement. This result is a new result and uncomparable to the approximation ratio obtained by randomized rounding method. The design and analysis of this algorithm fits in the framework of multiplicative weights update method, proposed by Arora et al. recently.; http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000252392300071&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=8e1609b174ce4e31116a60747a720701 ; Mathematics, Applied; CPCI-S(ISTP); 0
语种	英语
内容类型	其他
源URL	[http://ir.pku.edu.cn/handle/20.500.11897/388444]
专题	信息科学技术学院
推荐引用方式 GB/T 7714	Cui, Peng,Liu, Tian,Qian, Liyan,et al. Breadth first greedy algorithm for unconstrained set multicover. 2007-01-01.

个性服务

查看访问统计

相关权益政策

暂无数据

收藏/分享

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。