Online Two Stage k-Search Problem and Its Competitive Analysis

doi:10.1142/S01200511M500210

CORC > 上海财经大学 > 上海财经大学

	Online Two Stage k-Search Problem and Its Competitive Analysis
	Zhang, Wenming 1; Zhang, E.2; Zheng, Feifeng 3
刊名	INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE
	2016-09
卷号	27 期号:6 页码:653-663
关键词	Combinatorial optimization online search problem time series search online algorithm competitive ratio
ISSN号	0129-0541
DOI	10.1142/S01200511M500210
英文摘要	This work investigates an online two stage k-search problem where an online player makes selections in two stages. In the first stage a number of more than k quoted prices are selected as candidates, and then exactly k highest quoted prices are chosen from the candidates in the second stage. The objective is to maximize the total profit of the k final accepted prices. We mainly propose a deterministic online algorithm and prove that it is optimal in competitiveness. A further discussion is given considering various relationships between the value of k and the number of candidates.
WOS研究方向	Computer Science
语种	英语
出版者	WORLD SCIENTIFIC PUBL CO PTE LTD
WOS记录号	WOS:000392125100001
内容类型	期刊论文
源URL	[http://10.2.47.112/handle/2XS4QKH4/1214]
专题	上海财经大学
通讯作者	Zhang, E.
作者单位	1.Northwest Univ Xian, Sch Econ & Management, Xian 710127, Shaanxi, Peoples R China; 2.Shanghai Univ Finance & Econ, Sch Information Management & Engn, Shanghai 200433, Peoples R China; 3.Donghua Univ, Glorious Sun Sch Business & Managernent, Shanghai 200051, Peoples R China
推荐引用方式 GB/T 7714	Zhang, Wenming,Zhang, E.,Zheng, Feifeng. Online Two Stage k-Search Problem and Its Competitive Analysis[J]. INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE,2016,27(6):653-663.
APA	Zhang, Wenming,Zhang, E.,&Zheng, Feifeng.(2016).Online Two Stage k-Search Problem and Its Competitive Analysis.INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE,27(6),653-663.
MLA	Zhang, Wenming,et al."Online Two Stage k-Search Problem and Its Competitive Analysis".INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 27.6(2016):653-663.