A Tale of Santa Claus, Hypergraphs and Matroids
A Tale of Santa Claus, Hypergraphs and Matroids
复制标题
圣诞老人、超图和拟阵的故事
DOI：
10.1137/1.9781611975994.167
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Zhang, Yihao
中科院分区：
文献类型：
--
作者：
Davies, Sami;Rothvoss, Thomas Rothvoss;Zhang, Yihao
调度和近似算法中的一个众所周知的问题是圣诞老人问题。假设圣诞老人有一套礼物，他想把它们分配给一组孩子，这样最不快乐的孩子就会尽可能地快乐。这里，孩子对于Presji的值是Formpijϵ{0，pj}。Annamalai等人提出的多项式时间算法。给出了一个12.33-近似，并基于对Haxell的超图匹配论证的一种修正.在这篇文章中，我们引入了圣诞老人问题的变种.我们的算法也是基于Haxell的增广树，但随着拟阵结构的引入，我们用更简洁的方法解决了一个更一般的问题。然后，我们的结果可以作为一个黑盒来获得圣诞老人的(4+ϵ)-近似。这一因素也与圣诞老人的自然、紧凑的LP进行了比较。
A well-known problem in scheduling and approximation algorithms is the Santa Claus problem. Suppose that Santa Claus has a set of gifts, and he wants to distribute them among a set of children so that the least happy child is made as happy as possible. Here, the value that a childihas for a presentjis of the formpijϵ {0,pj}. A polynomial time algorithm by Annamalai et al. gives a 12.33-approximation and is based on a modification of Haxell's hypergraph matching argument.In this paper, we introduce amatroidversion of the Santa Claus problem. Our algorithm is also based on Haxell's augmenting tree, but with the introduction of the matroid structure we solve a more general problem with cleaner methods. Our result can then be used as a blackbox to obtain a (4 +ϵ)-approximation for Santa Claus. This factor also compares against a natural, compact LP for Santa Claus.
登录
查看更多内容
DOI：
10.1007/978-0-387-30162-4_28
发表时间：
2021-08
期刊：
Proceedings of the 1997 International Symposium on Parallel Architectures, Algorithms and Networks (I-SPAN'97)
影响因子：
--
作者：
通讯作者：
--
关于在不相关机器上进行调度的配置-LP
影响因子：
2
作者：
José Verschae;Andreas Wiese
通讯作者：
Andreas Wiese
DOI：
10.1145/1993636.1993718
发表时间：
2010-11
期刊：
Proceedings of the forty-third annual ACM symposium on Theory of computing
影响因子：
--
作者：
O. Svensson
通讯作者：
O. Svensson
关于受限圣诞老人配置LP完整性差距的说明
DOI：
10.1016/j.ipl.2020.106025
发表时间：
2018
期刊：
ArXiv
影响因子：
--
作者：
K. Jansen;L. Rohwedder
通讯作者：
L. Rohwedder
分配问题的紧凑 LP 松弛
DOI：
10.4230/oasics.sosa.2018.11
发表时间：
2018
期刊：
影响因子：
--
作者：
K. Jansen;L. Rohwedder
通讯作者：
L. Rohwedder