版权所有:内蒙古大学图书馆 技术提供:维普资讯• 智图
内蒙古自治区呼和浩特市赛罕区大学西街235号 邮编: 010021
学位级别:Ph.D.
导师姓名:Nagarajan, Viswanath
授予年度:2019年
主 题:Approximation algorithm Linear programming Stochastic optimization Online algorithm Network design Thesis
摘 要:This thesis presents linear and convex programming based algorithms for NP-hard discrete optimization problems, mainly with applications in network design. Network design problems aim to find a minimal/maximal weighted subgraph satisfying given properties. The problems studied include maximum cut, buy-at-bulk network design, throughput maximization, and unrelated machine scheduling. This thesis considers different models of input uncertainty: the traditional deterministic setting, the online setting where inputs arrive over time and the stochastic setting where inputs are drawn from some probability distribution. Our approach to these problems involves solving suitable convex relaxations and then using rounding procedures to convert the fractional solutions to integer solutions. The specific contributions of this thesis include (1) approximation algorithms for a constrained variant of the maximum cut problem using the Sherali-Adams LP hierarchy; (2) online primal-dual algorithms for covering and packing with Lq norm objectives; (3) approximation algorithms for stochastic unrelated machine scheduling.