The Complexity of Optimization on Grids

doi:10.1007/s00453-019-00587-4

	The Complexity of Optimization on Grids
	Barba, Luis 1; Milatz, Malte ; Nummenpalo, Jerri ; Sun, Xiaoming 2,3; Thomas, Antonis ; Zhang, Jialin 2,3; Zhang, Zhijie 2,3
	2019-09-01
发表期刊	ALGORITHMICA
ISSN	0178-4617
卷号	81 期号:9 页码:3494-3518
摘要	Unique-sink orientations of grids are models for linear optimization problems. Vertices of the grid represent possible solutions to the optimization problem; edge orientations indicate improving directions. The computational goal is to find the unique sink, representing the optimal solution. We study the query complexity of this model, where we consider two natural types of queries, vertex queries and edge queries. We describe a deterministic algorithm showing that the vertex query complexity of d-dimensional grids is O(n left ceiling d/2 right ceiling verhead. Our algorithms rely on structural results with potential further applications in optimization theory.
关键词	Unique-sink orientation Optimization Linear programming
DOI	10.1007/s00453-019-00587-4
收录类别	SCI
语种	英语
资助项目	National Natural Science Foundation of China[61433014] ; National Natural Science Foundation of China[61832003] ; National Natural Science Foundation of China[61761136014] ; National Natural Science Foundation of China[61872334] ; National Natural Science Foundation of China[61502449] ; 973 Program of China[2016YFB1000201]
WOS研究方向	Computer Science ; Mathematics
WOS类目	Computer Science, Software Engineering ; Mathematics, Applied
WOS记录号	WOS:000481768400005
出版者	SPRINGER
引用统计
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/4759
专题	中国科学院计算技术研究所期刊论文_英文
作者单位	1.Swiss Fed Inst Technol, Dept Comp Sci, Zurich, Switzerland 2.Chinese Acad Sci, Inst Comp Technol, CAS Key Lab Network Data Sci & Technol, Beijing 100190, Peoples R China 3.Univ Chinese Acad Sci, Beijing 100049, Peoples R China
推荐引用方式 GB/T 7714	Barba, Luis,Milatz, Malte,Nummenpalo, Jerri,et al. The Complexity of Optimization on Grids[J]. ALGORITHMICA,2019,81(9):3494-3518.
APA	Barba, Luis.,Milatz, Malte.,Nummenpalo, Jerri.,Sun, Xiaoming.,Thomas, Antonis.,...&Zhang, Zhijie.(2019).The Complexity of Optimization on Grids.ALGORITHMICA,81(9),3494-3518.
MLA	Barba, Luis,et al."The Complexity of Optimization on Grids".ALGORITHMICA 81.9(2019):3494-3518.