会员服务
近似 · 博弈论 ·
2021 年 3 月 18 日
A constant-factor approximation algorithm for Nash Social Welfare with submodular valuations
翻译：Nash社会福利局的固定要素近似算法,加上子模块估值
Wenzheng Li,Jan Vondrák
Wenzheng Li,Jan Vondrák

We present a $380$-approximation algorithm for the Nash Social Welfare problem with submodular valuations. Our algorithm builds on and extends a recent constant-factor approximation for Rado valuations.


翻译：我们对纳什(Nash)的社会福利问题和亚模式估值提出了380美元的接近算法。 我们的算法基于并扩展了最近拉多(Rado)估值的不变因素近似值。
0
下载
关闭预览

相关内容

ICLR 2021杰出论文奖出炉，8篇论文上榜！
专知会员服务
25+阅读 · 2021年4月2日
INRIA 最新《机器学习理论》课程笔记，176页pdf
专知会员服务
50+阅读 · 2020年12月14日
不可错过！UIUC最新《统计强化学习》课程！
专知会员服务
52+阅读 · 2020年9月7日
最新《非光滑优化》十讲硬核课程，剑桥大学梁经纬博士主讲
最新《非光滑优化》十讲硬核课程，剑桥大学梁经纬博士主讲
专知会员服务
31+阅读 · 2020年8月14日
生成性对抗网络:理论模型、评估指标和最近发展的概述，Generative Adversarial Networks (GANs): An Overview of Theoretical Model, Evaluation Metrics, and Recent Developments
生成性对抗网络:理论模型、评估指标和最近发展的概述，Generative Adversarial Networks (GANs): An Overview of Theoretical Model, Evaluation Metrics, and Recent Developments
专知会员服务
40+阅读 · 2020年5月30日
【普林斯顿大学-微软】加权元学习，Weighted Meta-Learning
【普林斯顿大学-微软】加权元学习，Weighted Meta-Learning
专知会员服务
39+阅读 · 2020年3月25日
深度强化学习策略梯度教程，53页ppt
深度强化学习策略梯度教程，53页ppt
专知会员服务
178+阅读 · 2020年2月1日
【2020密歇根大学论文】基于学习的序列决策算法的公平性综述论文，Fairness in Learning-Based Sequential Decision Algorithms: A Survey
【2020密歇根大学论文】基于学习的序列决策算法的公平性综述论文，Fairness in Learning-Based Sequential Decision Algorithms: A Survey
专知会员服务
21+阅读 · 2020年1月15日
【CGAN论文笔记强烈推荐】 基于CGAN的人脸深度图估计： Face Depth Estimation With Conditional Generative Adversarial Networks
专知会员服务
23+阅读 · 2020年1月8日
Stabilizing Transformers for Reinforcement Learning
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
图分类相关资源大列表
图分类相关资源大列表
专知
11+阅读 · 2019年7月18日
Hierarchically Structured Meta-learning
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
19篇ICML2019论文摘录选读！
19篇ICML2019论文摘录选读！
专知
28+阅读 · 2019年4月28日
已删除
已删除
将门创投
3+阅读 · 2019年4月12日
逆强化学习-学习人先验的动机
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
meta learning 17年：MAML SNAIL
meta learning 17年：MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
RL 真经
RL 真经
CreateAMind
5+阅读 · 2018年12月28日
CCF C类 | IJCNN 2019 Special Section : 信息论与深度学习
CCF C类 | IJCNN 2019 Special Section : 信息论与深度学习
Call4Papers
5+阅读 · 2018年12月7日
【论文推荐】最新六篇主题模型相关论文—领域特定知识库、神经变分推断、动态和静态主题模型
【论文推荐】最新六篇主题模型相关论文—领域特定知识库、神经变分推断、动态和静态主题模型
专知
19+阅读 · 2018年6月26日
Reinforcement Learning: An Introduction 2018第二版 500页
Reinforcement Learning: An Introduction 2018第二版 500页
CreateAMind
11+阅读 · 2018年4月27日
A 3-approximation list scheduling algorithm for a single-machine scheduling problem with a non-renewable resource and total weighted completion time criterion
Arxiv
0+阅读 · 2021年5月11日
Algorithms for the Minimum Dominating Set Problem in Bounded Arboricity Graphs: Simpler, Faster, and Combinatorial
Arxiv
0+阅读 · 2021年5月10日
Approximating Multistage Matching Problems
Arxiv
0+阅读 · 2021年5月10日
New Approximations and Hardness Results for Submodular Partitioning Problems
Arxiv
0+阅读 · 2021年5月10日
Approximation Theory Based Methods for RKHS Bandits
Arxiv
0+阅读 · 2021年5月10日
A (Slightly) Improved Approximation Algorithm for Metric TSP
Arxiv
0+阅读 · 2021年5月8日
Equivalent formulations of the oxygen depletion problem, other implicit free boundary value problems, and implications for numerical approximation
Arxiv
0+阅读 · 2021年5月7日
An Optimal Algorithm for Triangle Counting
Arxiv
0+阅读 · 2021年5月4日
Regret Bounds for Stochastic Shortest Path Problems with Linear Function Approximation
Arxiv
0+阅读 · 2021年5月4日
A fast algorithm with minimax optimal guarantees for topic models with an unknown number of topics
Arxiv
7+阅读 · 2018年6月12日
VIP会员
文章信息
前往arXiv
下载PDF
相关主题
近似
博弈论
相关VIP内容
ICLR 2021杰出论文奖出炉，8篇论文上榜！
专知会员服务
25+阅读 · 2021年4月2日
INRIA 最新《机器学习理论》课程笔记，176页pdf
专知会员服务
50+阅读 · 2020年12月14日
不可错过！UIUC最新《统计强化学习》课程！
专知会员服务
52+阅读 · 2020年9月7日
最新《非光滑优化》十讲硬核课程，剑桥大学梁经纬博士主讲
最新《非光滑优化》十讲硬核课程，剑桥大学梁经纬博士主讲
专知会员服务
31+阅读 · 2020年8月14日
生成性对抗网络:理论模型、评估指标和最近发展的概述，Generative Adversarial Networks (GANs): An Overview of Theoretical Model, Evaluation Metrics, and Recent Developments
生成性对抗网络:理论模型、评估指标和最近发展的概述，Generative Adversarial Networks (GANs): An Overview of Theoretical Model, Evaluation Metrics, and Recent Developments
专知会员服务
40+阅读 · 2020年5月30日
【普林斯顿大学-微软】加权元学习，Weighted Meta-Learning
【普林斯顿大学-微软】加权元学习，Weighted Meta-Learning
专知会员服务
39+阅读 · 2020年3月25日
深度强化学习策略梯度教程，53页ppt
深度强化学习策略梯度教程，53页ppt
专知会员服务
178+阅读 · 2020年2月1日
【2020密歇根大学论文】基于学习的序列决策算法的公平性综述论文，Fairness in Learning-Based Sequential Decision Algorithms: A Survey
【2020密歇根大学论文】基于学习的序列决策算法的公平性综述论文，Fairness in Learning-Based Sequential Decision Algorithms: A Survey
专知会员服务
21+阅读 · 2020年1月15日
【CGAN论文笔记强烈推荐】 基于CGAN的人脸深度图估计： Face Depth Estimation With Conditional Generative Adversarial Networks
专知会员服务
23+阅读 · 2020年1月8日
Stabilizing Transformers for Reinforcement Learning
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
热门VIP内容
相关资讯
图分类相关资源大列表
图分类相关资源大列表
专知
11+阅读 · 2019年7月18日
Hierarchically Structured Meta-learning
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
19篇ICML2019论文摘录选读！
19篇ICML2019论文摘录选读！
专知
28+阅读 · 2019年4月28日
已删除
已删除
将门创投
3+阅读 · 2019年4月12日
逆强化学习-学习人先验的动机
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
meta learning 17年：MAML SNAIL
meta learning 17年：MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
RL 真经
RL 真经
CreateAMind
5+阅读 · 2018年12月28日
CCF C类 | IJCNN 2019 Special Section : 信息论与深度学习
CCF C类 | IJCNN 2019 Special Section : 信息论与深度学习
Call4Papers
5+阅读 · 2018年12月7日
【论文推荐】最新六篇主题模型相关论文—领域特定知识库、神经变分推断、动态和静态主题模型
【论文推荐】最新六篇主题模型相关论文—领域特定知识库、神经变分推断、动态和静态主题模型
专知
19+阅读 · 2018年6月26日
Reinforcement Learning: An Introduction 2018第二版 500页
Reinforcement Learning: An Introduction 2018第二版 500页
CreateAMind
11+阅读 · 2018年4月27日
相关论文
A 3-approximation list scheduling algorithm for a single-machine scheduling problem with a non-renewable resource and total weighted completion time criterion
Arxiv
0+阅读 · 2021年5月11日
Algorithms for the Minimum Dominating Set Problem in Bounded Arboricity Graphs: Simpler, Faster, and Combinatorial
Arxiv
0+阅读 · 2021年5月10日
Approximating Multistage Matching Problems
Arxiv
0+阅读 · 2021年5月10日
New Approximations and Hardness Results for Submodular Partitioning Problems
Arxiv
0+阅读 · 2021年5月10日
Approximation Theory Based Methods for RKHS Bandits
Arxiv
0+阅读 · 2021年5月10日
A (Slightly) Improved Approximation Algorithm for Metric TSP
Arxiv
0+阅读 · 2021年5月8日
Equivalent formulations of the oxygen depletion problem, other implicit free boundary value problems, and implications for numerical approximation
Arxiv
0+阅读 · 2021年5月7日
An Optimal Algorithm for Triangle Counting
Arxiv
0+阅读 · 2021年5月4日
Regret Bounds for Stochastic Shortest Path Problems with Linear Function Approximation
Arxiv
0+阅读 · 2021年5月4日
A fast algorithm with minimax optimal guarantees for topic models with an unknown number of topics
Arxiv
7+阅读 · 2018年6月12日
Top
微信扫码咨询专知VIP会员
Top