随机组合优化问题的期望效用最大化

Dec, 2010

随机组合优化问题的期望效用最大化

Maximizing Expected Utility for Stochastic Combinatorial Optimization Problems

Jian Li, Amol Deshpande

TL;DR该研究考虑了一类随机组合优化问题，其中输入数据集中的元素权重不确定，并提出了一种基于预期效用的解决方案，以最大化某些给定实用函数的预期效益，并证明了在问题的精确版本下，可以针对几种重要的实用函数类得到多项式时间逼近算法。

Abstract

We study the stochastic versions of a broad class of combinatorial problems where the weights of the elements in the input dataset are uncertain. The class of problems that we study includes shortest paths, minimum weight spanning trees, and minimum weight matchings, and other combinatorial problems like knapsack. We observe that the expected value is inadeq

stochastic combinatorial problems expected utility maximization approximation algorithms risk-averse risk-prone

发现论文，激发创造

泊松逼近的随机组合优化

研究了多个随机组合问题，包括期望效用最大化问题、随机背包问题和随机装箱问题，并提出 Poisson 逼近技术以求解这些问题。

Nov, 2012

通过多项式估计进行随机子模最大化

本研究以连续贪心算法为基础，研究了具有一般性骨架约束的随机子模最大化问题，主要应用于在线学习，团队形成，设施位置，影响最大化，主动学习和感知目标函数。实验表明，使用多项式梯度估计代替样本估计，可有效减少随机性并缩短执行时间。

Mar, 2023

社会福利的自适应最大化

旨在最大化社会福利，我们研究重复选择政策的问题，由私人效用和公共收入构成的加权和。通过实验证明，我们获得了与误差下界相匹配的上界，表明福利最大化比多臂赌博问题更困难，且我们的算法实现了最佳速率。

Oct, 2023

优化具有变量不确定性的概率约束子模问题

本文研究了确定性设定中的概率约束子模优化问题，提出了一种新的分析方法，并提供了贪心算法来近似求解最优解。在实验中，演示了算法在几个最大覆盖问题和影响力最大化问题上的有效性。

Sep, 2023

没有效用函数的效益主义者：仅使用序数偏好最大化图问题的社会福利 - 全版

通过对经验偏好信息的分析，研究了多智能体系统中的最大效用解计算问题，该问题考虑了代理连接效用的多样性和约束性质，并证明基于有限的偏序信息可以实现接近于最优的解，特别地，最大生成树、最大权重平面子图、最佳旅行商问题和各种匹配问题都可以实现 2 - 近似度的计算。

Nov, 2017

鲁棒组合优化的随机化策略

本文研究了一类鲁棒优化问题，提出了两种设计逼近算法的方案，一种适用于线性目标函数的问题，另一种则基于乘性权重更新方法，并证明了这些算法在特定条件下具有不错的逼近比例，可用于求解离散优化问题中的独立集、子模函数等问题。

May, 2018

次模最大化的梯度方法

本文研究了许多学习应用中天然存在的连续子模函数的最大化问题，证明了随机投影梯度方法在凸约束下可以提供强的逼近保证，然后将其应用于随机子模函数的最大化问题，最后通过实验证明了该方法的有效性和实用性。

Aug, 2017

随机子模极大化：覆盖函数的情形

该论文研究了如何将随机梯度下降等连续优化算法应用到离散问题中的子模优化，通过将扩展线性化处理并通过向上投影处理，得到离散解，针对加权覆盖函数进行研究，实验表明，该方法在保证最优近似率的同时，大幅降低了计算成本。

Nov, 2017

当 LP 成为解决你的匹配烦恼的良方：随机匹配的改进界限

本研究研究了一种随机图模型和匹配问题，提出了基于线性规划和贪心的近似算法，并探讨了匹配问题在肾脏交流和在线广告上的应用。

Aug, 2010

正式化运行时分布的偏好

该论文旨在通过形式化运行时分布的喜好来解决在算法选择中的竞争。我们提出了一种基于效用理论的方法，描述了算法偏好的评分函数，这些函数依赖于解决问题的价值如何随时间降低以及满足的时间分布。我们展示了实用程序函数的例子，并展示了如何利用最大熵方法来建模未规定的时间分布，最后，我们展示了如何从运行时样本中高效估计算法的预期效用。

May, 2022