Collaborative Research: AF: Medium: Modern Combinatorial Optimization: Incentives, Uncertainty, and Smoothed Analysis

合作研究:AF:中:现代组合优化:激励、不确定性和平滑分析

基本信息

  • 批准号:
    1955205
  • 负责人:
  • 金额:
    $ 40万
  • 依托单位:
  • 依托单位国家:
    美国
  • 项目类别:
    Continuing Grant
  • 财政年份:
    2020
  • 资助国家:
    美国
  • 起止时间:
    2020-07-01 至 2024-06-30
  • 项目状态:
    已结题

项目摘要

Optimization theory is a central facet of computer science, and has driven the theoretical foundations since its inception. The classical paradigm considers a decision maker with all the relevant information available, and algorithms are evaluated primarily on the quality of the solution produced and the speed with which the solution is found. In modern applications, however, the decision maker no longer has all the relevant information in advance. Perhaps they must instead incentivize strategic agents to reveal this information, even when these agents have their own interests in the solution produced. Perhaps they must instead learn the relevant information in pieces online, making irrevocable decisions along the way with only partial information. The overarching theme of this project is the development of novel optimization theory subject to these modern constraints.In more detail, this project considers three key angles. First, it considers the interaction between multi-item auctions and communication complexity. For example, it aims to understand whether or not any communication-efficient optimization algorithm, designed without incentives in mind, can be made to also accommodate agents’ incentives without (much) loss in performance. Second, it revisits the classical problem of submodular maximization subject to a cardinality constraint (which is known to be intractable on worst case inputs), and introduces a novel variant of smoothed analysis for this problem. Finally, it proposes a new approach towards the still-open Matroid Secretary Problem: a generalization of the Minimum Spanning Tree problem where edges are learned one at a time and must be irrevocably included (or not) in the spanning tree before seeing other edges.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.
优化理论是计算机科学的一个核心方面,从一开始就推动了理论基础的发展。经典范式认为决策者拥有所有可用的相关信息,算法主要根据产生的解决方案的质量和找到解决方案的速度进行评估。然而,在现代应用中,决策者不再事先掌握所有相关信息。也许他们必须激励战略代理来透露这些信息,即使这些代理在所产生的解决方案中有自己的利益。也许他们必须在网上零碎地学习相关信息,在只有部分信息的情况下做出不可撤销的决定。该项目的总体主题是在这些现代约束下发展新的优化理论。更详细地说,这个项目考虑了三个关键的角度。首先,它考虑了多物品拍卖之间的相互作用和通信复杂性。例如,它的目的是了解是否可以在没有考虑激励的情况下设计任何通信效率优化算法,以适应代理的激励而不(太多)损失性能。其次,它重新审视了受基数约束的次模最大化的经典问题(已知在最坏情况下输入是难以处理的),并引入了该问题的平滑分析的新变体。最后,提出了一种解决仍然开放的矩阵秘书问题的新方法:对最小生成树问题的推广,其中每次学习一条边,并且在看到其他边之前必须不可撤销地包含(或不包含)在生成树中。该奖项反映了美国国家科学基金会的法定使命,并通过使用基金会的知识价值和更广泛的影响审查标准进行评估,被认为值得支持。

项目成果

期刊论文数量(4)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
Exponential communication separations between notions of selfishness
自私观念之间的指数级沟通差距
  • DOI:
    10.1145/3406325.3451127
  • 发表时间:
    2021
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Rubinstein, Aviad;Saxena, Raghuvansh R.;Thomas, Clayton;Weinberg, S. Matthew;Zhao, Junyao
  • 通讯作者:
    Zhao, Junyao
Implementation in Advised Strategies: Welfare Guarantees from Posted-Price Mechanisms When Demand Queries Are NP-Hard
建议策略的实施:当需求查询是 NP 困难时,定价机制的福利保证
Optimal Item Pricing in Online Combinatorial Auctions
在线组合拍卖中的最优物品定价
Formal Barriers to Simple Algorithms for the Matroid Secretary Problem
拟阵秘书问题简单算法的形式障碍
{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ monograph.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ sciAawards.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ conferencePapers.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ patent.updateTime }}

Seth Weinberg其他文献

Substrate Viscosity Dictates Cellular Response
  • DOI:
    10.1016/j.bpj.2018.11.2236
  • 发表时间:
    2019-02-15
  • 期刊:
  • 影响因子:
  • 作者:
    Thomas J. Petet;Halston Deal;Ariana DeCastro;Christina Tang;Seth Weinberg;Christopher Lemmon
  • 通讯作者:
    Christopher Lemmon
Cellular Adhesions Predict Mobility Propensities of EMT
  • DOI:
    10.1016/j.bpj.2017.11.3580
  • 发表时间:
    2018-02-02
  • 期刊:
  • 影响因子:
  • 作者:
    Lewis Scott;Christopher Lemmon;Seth Weinberg
  • 通讯作者:
    Seth Weinberg

Seth Weinberg的其他文献

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

{{ truncateString('Seth Weinberg', 18)}}的其他基金

CAREER: Towards a Predictive Theory of Algorithmic Mechanism Design
职业:算法机制设计的预测理论
  • 批准号:
    1942497
  • 财政年份:
    2020
  • 资助金额:
    $ 40万
  • 项目类别:
    Continuing Grant
NSF Student Travel Grant for 2019 Algorithmic Game Theory (AGT) Mentoring Workshop Co-Located with Economics and Computation (EC)
NSF 学生旅费资助 2019 年算法博弈论 (AGT) 辅导研讨会与经济学和计算 (EC) 同期举办
  • 批准号:
    1930734
  • 财政年份:
    2019
  • 资助金额:
    $ 40万
  • 项目类别:
    Standard Grant
AF: Small: Duality-based tools for simple vs. optimal mechanism design and applications to cryptocurrency
AF:小型:基于对偶的工具,用于简单与最优的机制设计和加密货币应用
  • 批准号:
    1717899
  • 财政年份:
    2017
  • 资助金额:
    $ 40万
  • 项目类别:
    Standard Grant

相似国自然基金

Research on Quantum Field Theory without a Lagrangian Description
  • 批准号:
    24ZR1403900
  • 批准年份:
    2024
  • 资助金额:
    0.0 万元
  • 项目类别:
    省市级项目
Cell Research
  • 批准号:
    31224802
  • 批准年份:
    2012
  • 资助金额:
    24.0 万元
  • 项目类别:
    专项基金项目
Cell Research
  • 批准号:
    31024804
  • 批准年份:
    2010
  • 资助金额:
    24.0 万元
  • 项目类别:
    专项基金项目
Cell Research (细胞研究)
  • 批准号:
    30824808
  • 批准年份:
    2008
  • 资助金额:
    24.0 万元
  • 项目类别:
    专项基金项目
Research on the Rapid Growth Mechanism of KDP Crystal
  • 批准号:
    10774081
  • 批准年份:
    2007
  • 资助金额:
    45.0 万元
  • 项目类别:
    面上项目

相似海外基金

Collaborative Research: AF: Medium: The Communication Cost of Distributed Computation
合作研究:AF:媒介:分布式计算的通信成本
  • 批准号:
    2402836
  • 财政年份:
    2024
  • 资助金额:
    $ 40万
  • 项目类别:
    Continuing Grant
Collaborative Research: AF: Medium: Foundations of Oblivious Reconfigurable Networks
合作研究:AF:媒介:遗忘可重构网络的基础
  • 批准号:
    2402851
  • 财政年份:
    2024
  • 资助金额:
    $ 40万
  • 项目类别:
    Continuing Grant
Collaborative Research: AF: Small: New Directions in Algorithmic Replicability
合作研究:AF:小:算法可复制性的新方向
  • 批准号:
    2342244
  • 财政年份:
    2024
  • 资助金额:
    $ 40万
  • 项目类别:
    Standard Grant
Collaborative Research: AF: Small: Exploring the Frontiers of Adversarial Robustness
合作研究:AF:小型:探索对抗鲁棒性的前沿
  • 批准号:
    2335411
  • 财政年份:
    2024
  • 资助金额:
    $ 40万
  • 项目类别:
    Standard Grant
NSF-BSF: Collaborative Research: AF: Small: Algorithmic Performance through History Independence
NSF-BSF:协作研究:AF:小型:通过历史独立性实现算法性能
  • 批准号:
    2420942
  • 财政年份:
    2024
  • 资助金额:
    $ 40万
  • 项目类别:
    Standard Grant
Collaborative Research: AF: Medium: Algorithms Meet Machine Learning: Mitigating Uncertainty in Optimization
协作研究:AF:媒介:算法遇见机器学习:减轻优化中的不确定性
  • 批准号:
    2422926
  • 财政年份:
    2024
  • 资助金额:
    $ 40万
  • 项目类别:
    Continuing Grant
Collaborative Research: AF: Small: Structural Graph Algorithms via General Frameworks
合作研究:AF:小型:通过通用框架的结构图算法
  • 批准号:
    2347322
  • 财政年份:
    2024
  • 资助金额:
    $ 40万
  • 项目类别:
    Standard Grant
Collaborative Research: AF: Small: Real Solutions of Polynomial Systems
合作研究:AF:小:多项式系统的实数解
  • 批准号:
    2331401
  • 财政年份:
    2024
  • 资助金额:
    $ 40万
  • 项目类别:
    Standard Grant
Collaborative Research: AF: Small: Real Solutions of Polynomial Systems
合作研究:AF:小:多项式系统的实数解
  • 批准号:
    2331400
  • 财政年份:
    2024
  • 资助金额:
    $ 40万
  • 项目类别:
    Standard Grant
Collaborative Research: AF: Medium: Fast Combinatorial Algorithms for (Dynamic) Matchings and Shortest Paths
合作研究:AF:中:(动态)匹配和最短路径的快速组合算法
  • 批准号:
    2402283
  • 财政年份:
    2024
  • 资助金额:
    $ 40万
  • 项目类别:
    Continuing Grant
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了