中国科学院机构知识库网格
Chinese Academy of Sciences Institutional Repositories Grid
首页 机构 成果 学者
  
  1. CAS IR Grid
  2. 计算技术研究所
  3. 中国科学院计算技术研究所
  4. 中国科学院计算技术研究所期刊论文
  5. 英文
The Complexity of Optimization on Grids

文献类型：期刊论文

作者Barba, Luis3; Milatz, Malte; Nummenpalo, Jerri; Sun, Xiaoming1,2; Thomas, Antonis; Zhang, Jialin1,2; Zhang, Zhijie1,2
刊名ALGORITHMICA
出版日期2019-09-01
卷号81期号:9页码:3494-3518
关键词Unique-sink orientation Optimization Linear programming
ISSN号0178-4617
DOI10.1007/s00453-019-00587-4
英文摘要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.
资助项目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记录号WOS:000481768400005
出版者SPRINGER
源URL[http://119.78.100.204/handle/2XEOYT63/4758]  
专题中国科学院计算技术研究所期刊论文_英文
作者单位1.Univ Chinese Acad Sci, Beijing 100049, Peoples R China
2.Chinese Acad Sci, Inst Comp Technol, CAS Key Lab Network Data Sci & Technol, Beijing 100190, Peoples R China
3.Swiss Fed Inst Technol, Dept Comp Sci, Zurich, Switzerland
推荐引用方式
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.

入库方式： OAI收割

来源：计算技术研究所

浏览0
下载0
收藏0
其他版本

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