论文标题
随机最小规范组合优化的近似算法
Approximation Algorithms for Stochastic Minimum Norm Combinatorial Optimization
论文作者
论文摘要
由于对数据的不确定性建模的需求和对数据的不确定性的兴趣，我们介绍和研究{\ em随机最小值优化}。我们有一个基本的组合优化问题，其中涉及的成本为{\ em随机变量}，并具有给定的分布；每个可行的解决方案都会诱导一个随机的多维成本向量，并给出一个目标函数，目标是找到一个最小化预期目标值的解决方案（不取决于成本的实现）。例如，在随机负载平衡中，需要将随机处理时间的作业分配给机器，而诱导的成本向量是机器负载向量。最近，在确定性的环境中，Chakrabarty和Swamy \ Cite {Chakrabartys19a}被认为是一系列相当广泛的目标，其中我们试图在给定的{\ em unutary单调的单调，对称性norm} $ f $下最小化成本向量的$ f $ norm。在随机最小值优化中，我们与这个广泛的目标合作，并寻求一种解决方案，以最大程度地减少诱导成本向量的{\ em预期$ f $ -norm}。 我们提供了一个通用框架，用于设计用于随机最小值组合优化的算法，使用该算法使用该算法，使用该算法，我们获得了载荷平衡和跨越树问题的随机最小值版本的近似算法。这项工作的两个关键技术贡献是：（1）独立兴趣连接随机最小值优化与同时优化（\ emph {small}）收集的预期$ \ mathsf {top} $ - $ \ ell $ -norms的结构结果； （2）显示如何解决预期的$ \ mathsf {top} $ - $ \ ell $ - $ - norm最小化，通过利用技术来最大程度地减少预期最大值，从而避免了$ \ mathsf {top} $ - $ \ ell $ norms造成的不可分离性质的困难。
Motivated by the need for, and growing interest in, modeling uncertainty in data, we introduce and study {\em stochastic minimum-norm optimization}. We have an underlying combinatorial optimization problem where the costs involved are {\em random variables} with given distributions; each feasible solution induces a random multidimensional cost vector, and given a certain objective function, the goal is to find a solution (that does not depend on the realizations of the costs) that minimizes the expected objective value. For instance, in stochastic load balancing, jobs with random processing times need to be assigned to machines, and the induced cost vector is the machine-load vector. Recently, in the deterministic setting, Chakrabarty and Swamy \cite{ChakrabartyS19a} considered a fairly broad suite of objectives, wherein we seek to minimize the $f$-norm of the cost vector under a given {\em arbitrary monotone, symmetric norm} $f$. In stochastic minimum-norm optimization, we work with this broad class of objectives, and seek a solution that minimizes the {\em expected $f$-norm} of the induced cost vector. We give a general framework for devising algorithms for stochastic minimum-norm combinatorial optimization, using which we obtain approximation algorithms for the stochastic minimum-norm versions of the load balancing and spanning tree problems. Two key technical contributions of this work are: (1) a structural result of independent interest connecting stochastic minimum-norm optimization to the simultaneous optimization of a (\emph{small}) collection of expected $\mathsf{Top}$-$\ell$-norms; and (2) showing how to tackle expected $\mathsf{Top}$-$\ell$-norm minimization by leveraging techniques used to deal with minimizing the expected maximum, circumventing the difficulties posed by the non-separable nature of $\mathsf{Top}$-$\ell$ norms.
