咨询与建议

看过本文的还看了

相关文献

该作者的其他文献

文献详情 >Linear and Convex Programming ... 收藏
Linear and Convex Programming Based Algorithms for Network D...

Linear and Convex Programming Based Algorithms for Network Design

基于线性规划和凸规划的网络设计算法

作     者:Shen, Xiangkun 

作者单位:University of Michigan 

学位级别: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.

读者评论 与其他读者分享你的观点

用户名:未登录
我的评分