Instance-sensitive robustness guarantees for sequencing with unknown packing and covering constraints
Instance-sensitive robustness guarantees for sequencing with unknown packing and covering constraints
复制标题
实例敏感的鲁棒性保证了未知包装和覆盖约束的测序
DOI：
10.1145/2422436.2422490
复制
发表时间：
--
期刊：
影响因子：
--
通讯作者：
J. Mestre.
中科院分区：
文献类型：
--
作者：
N. Megow;J. Mestre.
具有未知覆盖或打包约束的测序问题出现在各种应用中，例如，在运行时可用性不确定的实时计算环境中。当对于任何可能的约束，满足约束的序列的最大或最小前缀至多是来自最佳包装或覆盖的因子α时，序列被称为α-鲁棒的。众所周知，覆盖问题总是允许 4-鲁棒解，并且在某些情况下该因子是严格的。对于包装变体，一般不可能有这样恒定的鲁棒性因子。在这项工作中，我们解决了这样一个事实：许多问题实例可能比病态的最坏情况实例提供更好的鲁棒性保证。我们的目标是提供更有意义、对实例敏感的性能保证。我们提出了一种算法，为每个实例构建一个鲁棒性因子任意接近最优的解决方案。这意味着先前研究的问题（例如通用背包问题和不可靠机器上的通用调度）几乎是最优的解决方案。关键要素和主要结果是对给定目标函数的双值测序进行近乎精确的可行性测试。我们表明，决定确切的可行性是非常 NP 困难的，因此，除非 P=NP，否则我们的测试是最好的。我们希望实例敏感的性能保证的想法能够激发人们重新审视其他优化问题，并设计适合每个实例的算法。
Sequencing problems with an unknown covering or packing constraint appear in various applications, e.g., in real-time computing environments with uncertain run-time availability. A sequence is called α-robust when, for any possible constraint, the maximal or minimal prefix of the sequence that satisfies the constraint is at most a factor α from an optimal packing or covering. It is known that the covering problem always admits a 4-robust solution, and there are instances for which this factor is tight. For the packing variant no such constant robustness factor is possible in general. In this work we address the fact that many problem instances may allow for a much better robustness guarantee than the pathological worst case instances. We aim for more meaningful, instance-sensitive performance guarantees. We present an algorithm that constructs for each instance a solution with a robustness factor arbitrarily close to optimal. This implies nearly optimal solutions for previously studied problems such as the universal knapsack problem and for universal scheduling on an unreliable machine. The crucial ingredient and main result is a nearly exact feasibility test for dual-value sequencing with a given target function. We show that deciding exact feasibility is strongly NP-hard, and thus, our test is best possible, unless P=NP.We hope that the idea of instance-sensitive performance guarantees inspires to revisit other optimization problems and design algorithm tailored to perform well for each individual instance.
登录
查看更多内容
DOI：
10.1145/2160158.2160161
发表时间：
2012-04
期刊：
Electron. Colloquium Comput. Complex.
影响因子：
--
作者：
Oded Goldreich;Brendan Juba;M. Sudan
通讯作者：
Oded Goldreich;Brendan Juba;M. Sudan
DOI：
10.1137/110844210
发表时间：
2012-05
期刊：
SIAM J. Comput.
影响因子：
--
作者：
Julián Mestre;Nicole Megow
通讯作者：
Julián Mestre;Nicole Megow
通过柱生成恢复稳健性
DOI：
--
发表时间：
2011
期刊：
Embedded Systems and Applications
影响因子：
--
作者：
M. Akker;P. Bouman;H. Hoogeveen
通讯作者：
H. Hoogeveen
顺序 PAC 学习
DOI：
--
发表时间：
1995
期刊：
Annual Conference Computational Learning Theory
影响因子：
--
作者：
Dale Schuurmans;R. Greiner
通讯作者：
R. Greiner
DOI：
--
发表时间：
1992
期刊：
Annual Conference Computational Learning Theory
影响因子：
--
作者：
J. C. Jackson;A. Tomkins
通讯作者：
A. Tomkins