CAREER: Approximation and Hardness from Strong Relaxations

职业:强松弛的近似和硬度

基本信息

  • 批准号:
    1350196
  • 负责人:
  • 金额:
    $ 60万
  • 依托单位:
  • 依托单位国家:
    美国
  • 项目类别:
    Continuing Grant
  • 财政年份:
    2014
  • 资助国家:
    美国
  • 起止时间:
    2014-02-01 至 2019-01-31
  • 项目状态:
    已结题

项目摘要

Discrete optimization lies at the core of computer science and its applications. Except for a few special cases, exact optimization is computationally intractable. Approximation algorithms seek to resolve this issue by providing computational efficiency and at the same time provable guarantees on the quality of solutions. The current project addresses fundamental open questions about approximation algorithms. The project will use strong relaxations, especially the sum-of-squares method, as a lens to shed light on these questions.The Unique Games Conjecture has fueled many recent advances in our understanding of approximation algorithms. A proof of this conjecture would show that for a large classes of problems the approximation guarantees of a concrete algorithm are best possible. On the other hand, a refutation of the conjecture would likely lead to major improvements of approximation algorithms for a wide range of problems. Recent works of the PI and coauthors identified a candidate algorithm to refute the Unique Games Conjecture. This algorithm is able to solve previously proposed constructions of hard instances for problems that the conjecture predicts to be NP-hard. An integral part of the research project is to resolve whether this algorithm indeed refutes the conjecture.The candidate algorithm comes from a meta-algorithm, called sum-of-squares method. The current project will also study the approximation guarantees of this method beyond the Unique Games Conjecture, and investigate the thesis that for a large class of problems, the sum-of-squares method is an optimal meta-algorithm in terms of approximation guarantee and time complexity.A broad range of academic disciplines apply optimization techniques and computational efficiency is an important factor in these applications. In practice, meta-algorithms are often a popular choice, e.g., belief propagation, MCMC methods and SAT solvers, but lack provable approximation guarantees. The sum-of-squares method has the potential to achieve the same versatility as other meta-algorithms but with the additional benefit of provable guarantees.
离散优化是计算机科学及其应用的核心。除了少数特殊情况外,精确的最优化在计算上是困难的。近似算法试图通过提供计算效率,同时对解的质量提供可证明的保证来解决这一问题。当前的项目解决了关于近似算法的基本开放问题。该项目将使用强松弛,特别是平方和方法作为镜头来阐明这些问题。独特的游戏猜想推动了我们对近似算法的理解的许多最近的进步。这一猜想的证明将表明,对于一大类问题,一个具体算法的近似保证是最可能的。另一方面,对猜想的反驳可能会导致对广泛问题的近似算法的重大改进。PI和合著者最近的工作确定了一个候选算法来驳斥唯一的游戏猜想。对于猜想预测为NP难的问题,该算法能够解决以前提出的构造难实例的问题。研究项目的一个组成部分是解决该算法是否真的驳斥了猜想。候选算法来自一种称为平方和法的元算法。本项目还将研究这种方法的逼近保证,超越了唯一的Games猜想,并研究了对于一大类问题,平方和方法在逼近保证和时间复杂性方面是一种最优的元算法,广泛的学术学科应用了优化技术,计算效率是这些应用的重要因素。在实践中,元算法往往是一种流行的选择,如信任传播、MCMC方法和SAT求解器,但缺乏可证明的逼近保证。平方和方法有可能实现与其他元算法相同的通用性,但具有可证明的保证的额外好处。

项目成果

期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)

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

{{ 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 }}

Robert Kleinberg其他文献

Full surplus extraction from samples
  • DOI:
    10.1016/j.jet.2021.105230
  • 发表时间:
    2021-04-01
  • 期刊:
  • 影响因子:
  • 作者:
    Hu Fu;Nima Haghpanah;Jason Hartline;Robert Kleinberg
  • 通讯作者:
    Robert Kleinberg
Load is not what you should balance: Introducing Prequal
负载不是你应该平衡的:Prequal 简介
  • DOI:
    10.48550/arxiv.2312.10172
  • 发表时间:
    2023
  • 期刊:
  • 影响因子:
    0
  • 作者:
    B. Wydrowski;Robert Kleinberg;Stephen M. Rumble;Aaron Archer
  • 通讯作者:
    Aaron Archer
Scalabilitiy and Congestion Control in Oblivious Reconfigurable Networks
遗忘可重构网络中的可扩展性和拥塞控制
  • DOI:
  • 发表时间:
    2023
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Tegan Wilson;Hakim Weatherspoon;Robert Kleinberg
  • 通讯作者:
    Robert Kleinberg
Shale: A Practical, Scalable Oblivious Reconfigurable Network
Shale:实用、可扩展、可重构的网络
  • DOI:
  • 发表时间:
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Tegan Wilson;Robert Kleinberg;Hakim Weatherspoon;Daniel Amir;Nitika Saran;Vishal Shrivas
  • 通讯作者:
    Vishal Shrivas
Approximately optimal auctions for correlated bidders
  • DOI:
    10.1016/j.geb.2013.03.010
  • 发表时间:
    2015-07-01
  • 期刊:
  • 影响因子:
  • 作者:
    Shahar Dobzinski;Hu Fu;Robert Kleinberg
  • 通讯作者:
    Robert Kleinberg

Robert Kleinberg的其他文献

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

{{ truncateString('Robert Kleinberg', 18)}}的其他基金

Collaborative Research: AF: Medium: Foundations of Oblivious Reconfigurable Networks
合作研究:AF:媒介:遗忘可重构网络的基础
  • 批准号:
    2402851
  • 财政年份:
    2024
  • 资助金额:
    $ 60万
  • 项目类别:
    Continuing Grant
AF: Medium: Behavioral design for online environments
AF:中:在线环境的行为设计
  • 批准号:
    1512964
  • 财政年份:
    2015
  • 资助金额:
    $ 60万
  • 项目类别:
    Continuing Grant
CAREER: Algorithms for Environments with Incomplete Information
职业:不完整信息环境下的算法
  • 批准号:
    0643934
  • 财政年份:
    2007
  • 资助金额:
    $ 60万
  • 项目类别:
    Continuing Grant
Combinatorial and Algorithmic Aspects of Network Coding
网络编码的组合和算法方面
  • 批准号:
    0729102
  • 财政年份:
    2007
  • 资助金额:
    $ 60万
  • 项目类别:
    Standard Grant
PostDoctoral Research Fellowship
博士后研究奖学金
  • 批准号:
    0503297
  • 财政年份:
    2005
  • 资助金额:
    $ 60万
  • 项目类别:
    Fellowship Award

相似海外基金

AF: Small: Hardness of Approximation Meets Parameterized Complexity
AF:小:近似难度满足参数化复杂性
  • 批准号:
    2313372
  • 财政年份:
    2023
  • 资助金额:
    $ 60万
  • 项目类别:
    Standard Grant
Approximation Algorithms and Hardness of Approximation for Optimization Problems
优化问题的逼近算法和逼近难度
  • 批准号:
    RGPIN-2018-04677
  • 财政年份:
    2022
  • 资助金额:
    $ 60万
  • 项目类别:
    Discovery Grants Program - Individual
AF: Small: The Unique Games Conjecture and Related Problems in Hardness of Approximation
AF:小:独特的博弈猜想及近似难度中的相关问题
  • 批准号:
    2200956
  • 财政年份:
    2022
  • 资助金额:
    $ 60万
  • 项目类别:
    Standard Grant
AF: Small: Hardness of Approximation: Classical and New
AF:小:近似难度:经典和新
  • 批准号:
    2130816
  • 财政年份:
    2021
  • 资助金额:
    $ 60万
  • 项目类别:
    Standard Grant
Approximation Algorithms and Hardness of Approximation for Optimization Problems
优化问题的逼近算法和逼近难度
  • 批准号:
    RGPIN-2018-04677
  • 财政年份:
    2021
  • 资助金额:
    $ 60万
  • 项目类别:
    Discovery Grants Program - Individual
Approximation Algorithms and Hardness of Approximation for Optimization Problems
优化问题的逼近算法和逼近难度
  • 批准号:
    RGPIN-2018-04677
  • 财政年份:
    2020
  • 资助金额:
    $ 60万
  • 项目类别:
    Discovery Grants Program - Individual
Approximation Algorithms and Hardness of Approximation for Optimization Problems
优化问题的逼近算法和逼近难度
  • 批准号:
    RGPIN-2018-04677
  • 财政年份:
    2019
  • 资助金额:
    $ 60万
  • 项目类别:
    Discovery Grants Program - Individual
AF: Small: Analysis, Geometry, and Hardness of Approximation
AF:小:分析、几何和近似硬度
  • 批准号:
    1813438
  • 财政年份:
    2018
  • 资助金额:
    $ 60万
  • 项目类别:
    Standard Grant
Approximation Algorithms and Hardness of Approximation for Optimization Problems
优化问题的逼近算法和逼近难度
  • 批准号:
    RGPIN-2018-04677
  • 财政年份:
    2018
  • 资助金额:
    $ 60万
  • 项目类别:
    Discovery Grants Program - Individual
Approximation Algorithms and Hardness of Approximation for Optimization Problems
优化问题的逼近算法和逼近难度
  • 批准号:
    311704-2013
  • 财政年份:
    2017
  • 资助金额:
    $ 60万
  • 项目类别:
    Discovery Grants Program - Individual
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了