Complexity of optimizing over the integers
Complexity of optimizing over the integers
复制标题
整数优化的复杂性
DOI：
10.1007/s10107-022-01862-z
复制
发表时间：
2022
影响因子：
2.7
通讯作者：
Basu, Amitabh
中科院分区：
文献类型：
--
作者：
Basu, Amitabh
在本文的第一部分中，我们提出了一个统一的框架来分析任何优化问题的算法复杂度，无论它是连续的还是离散的。这有助于在一般数学优化的背景下形式化“输入”、“大小”和“复杂性”等概念，避免依赖于上下文的定义，这是连续和离散优化中处理复杂性的差异来源之一。在论文的第二部分，我们利用第一部分开发的语言研究了混合整数凸优化的信息论和算法复杂度，它作为一种特例，一方面包含连续凸优化，另一方面包含纯整数优化。我们力求在我们的阐述中尽量做到概括性。我们希望这篇论文包含的材料，连续优化器和离散优化器都发现新的和有趣的，即使几乎所有的材料是一个或另一个社区的常识。我们认为本文的主要优点是将所有这些信息汇集在一个统一的保护伞下，希望这将成为跨越连续-离散鸿沟的更多互动的另一种催化剂。事实上，我们写这篇论文第一部分的动机是为两个社区提供一种通用语言。
In the first part of this paper, we present a unified framework for analyzing the algorithmic complexity of any optimization problem, whether it be continuous or discrete in nature. This helps to formalize notions like “input”, “size” and “complexity” in the context of general mathematical optimization, avoiding context dependent definitions which is one of the sources of difference in the treatment of complexity within continuous and discrete optimization. In the second part of the paper, we employ the language developed in the first part to study information theoretic and algorithmic complexity ofmixed-integer convex optimization, which contains as a special case continuous convex optimization on the one hand and pure integer optimization on the other. We strive for the maximum possible generality in our exposition. We hope that this paper contains material that both continuous optimizers and discrete optimizers find new and interesting, even though almost all of the material presented is common knowledge in one or the other community. We see the main merit of this paper as bringing together all of this information under one unifying umbrella with the hope that this will act as yet another catalyst for more interaction across the continuous-discrete divide. In fact, our motivation behind Part I of the paper is to provide a common language for both communities.
登录
查看更多内容
DOI：
--
发表时间：
2012
期刊：
MOS-SIAM Series on Optimization
影响因子：
--
作者：
J. D. Loera;R. Hemmecke;M. Köppe
通讯作者：
M. Köppe
DOI：
--
发表时间：
2019
期刊：
arXiv.org
影响因子：
--
作者：
F. Eisenbrand;Christoph Hunkenschröder;Kim;Martin Koutecký;Asaf Levin;S. Onn
通讯作者：
S. Onn
影响因子：
2.7
作者：
Joseph Paat;Miriam Schlöter;R. Weismantel
通讯作者：
R. Weismantel
影响因子：
2.7
作者：
Timm Oertel
通讯作者：
Timm Oertel
影响因子：
0.6
作者：
Jean
通讯作者：
Jean