Estimating the Makespan of the Two-Valued Restricted Assignment Problem
Estimating the Makespan of the Two-Valued Restricted Assignment Problem
复制标题
估计二值限制分配问题的完工时间
作者：
K. Jansen;Kati Land;M. Maack
我们考虑不相关机器上的调度问题的特殊情况，即具有两个不同处理时间的受限分配问题。我们证明配置 LP 的完整性差距最多为 53≈1.667documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt}对于这个问题，egin{document}$$frac{5}{3} 大约为 1.667$$end{document}。这使我们能够在 53 倍内估计最佳制作时间documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$frac{5}{3}$$end{document}，改进了以前最著名的估计算法，比率为 116≈1.833documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$frac{11}{6} 大约1.833$$end{document} 由于 Chakrabarty 等人。 （参见：第二十六届 ACM-SIAM 离散算法年度研讨会论文集 (SODA 2015)，第 1087-1101 页，2015 年）。
We consider a special case of the scheduling problem on unrelated machines, namely the restricted assignment problem with two different processing times. We show that the configuration LP has an integrality gap of at most 53≈1.667documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$frac{5}{3} approx 1.667$$end{document} for this problem. This allows us to estimate the optimal makespan within a factor of 53documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$frac{5}{3}$$end{document}, improving upon the previously best known estimation algorithm with ratio 116≈1.833documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$frac{11}{6} approx 1.833$$end{document} due to Chakrabarty et al. (in: Proceedings of the twenty-sixth annual ACM-SIAM symposium on discrete algorithms (SODA 2015), pp 1087–1101, 2015).