Approximation algorithms for NP-hard problems

NP 困难问题的近似算法

基本信息

  • 批准号:
    RGPIN-2014-04351
  • 负责人:
  • 金额:
    $ 3.35万
  • 依托单位:
  • 依托单位国家:
    加拿大
  • 项目类别:
    Discovery Grants Program - Individual
  • 财政年份:
    2014
  • 资助国家:
    加拿大
  • 起止时间:
    2014-01-01 至 2015-12-31
  • 项目状态:
    已结题

项目摘要

Network design, network flows, and graph connectivity occur as core topics in Theoretical Computer Science, Operations Research, and Combinatorial Optimization. Many important algorithmic paradigms were developed in the context of these topics, such as the greedy algorithm for minimum spanning trees and the max-flow min-cut theorem for network flows. Moreover, these topics arise in many practical contexts such as the design of fault-tolerant communication networks and congestion control for urban road traffic. Many of the problems arising in practical contexts are NP-hard. This means that optimal solutions cannot be computed in a reasonable running time, modulo the P .not.= NP conjecture. Hence, research has focused on approximation algorithms, i.e., efficient algorithms that find solutions that are within a guaranteed factor of the optimal solution. My current and planned research focuses on the following three broad interlocking themes. I discuss two of these topics below, and my proposal discusses all the topics in full. 1. Design of approximately minimum-cost networks, including the Traveling Salesman Problem (TSP) and its variants. 2. Design of networks subject to node-connectivity requirements. 3. Lift-and-Project methods for the Asymmetric TSP and related problems. The most famous problem in all of discrete optimization is the TSP. The best known algorithmic result is the 3/2-approximation algorithm due to Christofides from 1976. It has long been conjectured that there exists a 4/3-approximation algorithm for the TSP, and that there exists a 3/2-approximation algorithm for a variant called the s-t path TSP. Two of the outstanding open questions on this topic that I am researching are the following: (*) Improve on the approximation guarantee of 7/5 for an important special case called the GRAPHIC TSP, possibly based on a combination of LP-rounding techniques and ear-decomposition techniques. (*) Improve on the approximation guarantee of 8/5 for the s-t path TSP, possibly based on LP-rounding techniques, coupled with improved structural results on the support graph of LP solutions. The second broad theme of my research addresses the design of networks subject to node-connectivity requirements. One of the basic problems in network design is to find a minimum-cost sub-network H of a given network G such that H satisfies some pre-specified connectivity requirements. The area of minimum-cost network design subject to EDGE-connectivity requirements flourished in the 1990s, and there were a number of landmark results. Progress has been much slower on similar problems with NODE-connectivity requirements, despite more than a decade of active research. Very recently, in a paper co-authored with L.Vegh (Proc. IEEE FOCS 2013), I have obtained a major advance on a fundamental problem in this area: we have a 6-approximation algorithm for the minimum-cost k-node connected spanning subgraph problem, assuming that the number of nodes is at least k^4. Our results and techniques have opened up many new directions in the design of networks subject to node-connectivity requirements. I plan to continue research on these topics, together with graduate students and postdocs. In summary, the high-level goal of my research agenda is to provide significant advances in the areas of Network Design and related areas of Combinatorial Optimization. This has the potential to improve the results and techniques available to all researchers who work in this core area of the computational sciences. Problems such as the TSP are ubiquitous in all modern societies, including Canada; the economy and infrastructure are based on logistics, transport, networks, and on the optimal allocation of scarce resources to critical tasks.
网络设计、网络流量和图形连通性是理论计算机科学、运筹学和组合优化的核心课题。许多重要的算法范例都是在这些主题的背景下发展起来的,例如最小生成树的贪婪算法和网络流的最大流最小割定理。此外,这些问题还出现在许多实际环境中,例如容错通信网络的设计和城市道路交通的拥塞控制。在实际环境中出现的许多问题都是NP难的。这意味着不能在合理的运行时间内计算最优解,模为P.no.=NP猜想。因此,研究集中在近似算法上,即找到在最优解的保证因子内的解的高效算法。我目前和计划的研究集中在以下三个广泛的相互关联的主题上。我在下面讨论了其中两个主题,我的提案全面讨论了所有主题。1.近似最小费用网络的设计,包括旅行商问题及其变种。2.满足节点连通性要求的网络设计。3.非对称TSP的Lift-and-Project方法及相关问题。在所有的离散优化中,最著名的问题是TSP问题。最著名的算法结果是1976年由Christofides提出的3/2近似算法。长期以来,人们一直猜想TSP存在一个4/3近似算法,并且存在一个称为S-t路TSP的变种的3/2近似算法。我正在研究的关于这个主题的两个悬而未决的问题如下:(*)改进了一种称为图TSP的重要特例的7/5的近似保证,可能基于Lp舍入技术和耳朵分解技术的组合。(*)改进了S-t路TSP的8/5的近似保证,可能基于Lp舍入技术,并改进了Lp解的支撑图的结构结果。我研究的第二个主要主题是满足节点连通性要求的网络设计。网络设计中的一个基本问题是寻找给定网络G的一个最小费用子网络H,使H满足某些预先指定的连通性要求。满足边缘连通性要求的最低成本网络设计领域在20世纪90年代蓬勃发展,取得了许多里程碑式的成果。尽管进行了十多年的积极研究,但在节点连接要求方面的类似问题上的进展要慢得多。最近,在与L.Vegh(Proc.在IEEE FOCS 2013)上,我在这个领域的一个基本问题上取得了重大进展:我们在假设节点数量至少为k^4的情况下,得到了最小代价k节点连通生成子图问题的6-近似算法。我们的结果和技术在满足节点连通性要求的网络设计中开辟了许多新的方向。我计划与研究生和博士后一起继续研究这些主题。总而言之,我的研究议程的高级目标是在网络设计领域和组合优化的相关领域提供重大进展。这有可能改善所有在计算科学这一核心领域工作的研究人员可用的结果和技术。像TSP这样的问题在包括加拿大在内的所有现代社会中无处不在;经济和基础设施的基础是物流、运输、网络和关键任务的稀缺资源的最佳分配。

项目成果

期刊论文数量(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 }}

Cheriyan, Joseph其他文献

Evaluation of Dynamic Contrast-Enhanced MRI Measures of Lung Congestion and Endothelial Permeability in Heart Failure: A Prospective Method Validation Study.
  • DOI:
    10.1002/jmri.28174
  • 发表时间:
    2022-08
  • 期刊:
  • 影响因子:
    4.4
  • 作者:
    Cheriyan, Joseph;Roberts, Alexandra;Roberts, Caleb;Graves, Martin J.;Patterson, Ilse;Slough, Rhys A.;Schroyer, Rosemary;Fernando, Disala;Kumar, Subramanya;Lee, Sarah;Parker, Geoffrey J. M.;Sarov-Blat, Lea;McEniery, Carmel;Middlemiss, Jessica;Sprecher, Dennis;Janiczek, Robert L.
  • 通讯作者:
    Janiczek, Robert L.
Therapeutic Potential of p38 MAP Kinase Inhibition in the Management of Cardiovascular Disease
  • DOI:
    10.1007/s40256-014-0063-6
  • 发表时间:
    2014-06-01
  • 期刊:
  • 影响因子:
    3
  • 作者:
    Fisk, Marie;Gajendragadkar, Parag R.;Cheriyan, Joseph
  • 通讯作者:
    Cheriyan, Joseph
Clinical Pharmacokinetics, Safety, and Tolerability of a Novel, First-in-Class TRPV4 Ion Channel Inhibitor, GSK2798745, in Healthy and Heart Failure Subjects
  • DOI:
    10.1007/s40256-018-00320-6
  • 发表时间:
    2019-06-01
  • 期刊:
  • 影响因子:
    3
  • 作者:
    Goyal, Navin;Skrdla, Pete;Cheriyan, Joseph
  • 通讯作者:
    Cheriyan, Joseph
Low-dose IL-2 enhances the generation of IL-10-producing immunoregulatory B cells.
  • DOI:
    10.1038/s41467-023-37424-w
  • 发表时间:
    2023-04-12
  • 期刊:
  • 影响因子:
    16.6
  • 作者:
    Inaba, Akimichi;Tuong, Zewen Kelvin;Zhao, Tian X. X.;Stewart, Andrew P. P.;Mathews, Rebeccah;Truman, Lucy;Sriranjan, Rouchelle;Kennet, Jane;Saeb-Parsy, Kourosh;Wicker, Linda;Waldron-Lynch, Frank;Cheriyan, Joseph;Todd, John A. A.;Mallat, Ziad;Clatworthy, Menna R. R.
  • 通讯作者:
    Clatworthy, Menna R. R.
Inducible nitric oxide synthase activity is increased in patients with rheumatoid arthritis and contributes to endothelial dysfunction
  • DOI:
    10.1016/j.ijcard.2008.02.011
  • 发表时间:
    2008-10-13
  • 期刊:
  • 影响因子:
    3.5
  • 作者:
    Maki-Petaja, Kaisa M.;Cheriyan, Joseph;Wilkinson, Ian B.
  • 通讯作者:
    Wilkinson, Ian B.

Cheriyan, Joseph的其他文献

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

{{ truncateString('Cheriyan, Joseph', 18)}}的其他基金

Approximation Algorithms for NP-Hard Problems
NP 困难问题的近似算法
  • 批准号:
    RGPIN-2019-04197
  • 财政年份:
    2022
  • 资助金额:
    $ 3.35万
  • 项目类别:
    Discovery Grants Program - Individual
Approximation Algorithms for NP-Hard Problems
NP 困难问题的近似算法
  • 批准号:
    RGPIN-2019-04197
  • 财政年份:
    2021
  • 资助金额:
    $ 3.35万
  • 项目类别:
    Discovery Grants Program - Individual
Approximation Algorithms for NP-Hard Problems
NP 困难问题的近似算法
  • 批准号:
    RGPIN-2019-04197
  • 财政年份:
    2020
  • 资助金额:
    $ 3.35万
  • 项目类别:
    Discovery Grants Program - Individual
Approximation Algorithms for NP-Hard Problems
NP 困难问题的近似算法
  • 批准号:
    RGPIN-2019-04197
  • 财政年份:
    2019
  • 资助金额:
    $ 3.35万
  • 项目类别:
    Discovery Grants Program - Individual
Approximation algorithms for NP-hard problems
NP 困难问题的近似算法
  • 批准号:
    RGPIN-2014-04351
  • 财政年份:
    2018
  • 资助金额:
    $ 3.35万
  • 项目类别:
    Discovery Grants Program - Individual
Approximation algorithms for NP-hard problems
NP 困难问题的近似算法
  • 批准号:
    RGPIN-2014-04351
  • 财政年份:
    2017
  • 资助金额:
    $ 3.35万
  • 项目类别:
    Discovery Grants Program - Individual
Approximation algorithms for NP-hard problems
NP 困难问题的近似算法
  • 批准号:
    RGPIN-2014-04351
  • 财政年份:
    2016
  • 资助金额:
    $ 3.35万
  • 项目类别:
    Discovery Grants Program - Individual
Approximation algorithms for NP-hard problems
NP 困难问题的近似算法
  • 批准号:
    RGPIN-2014-04351
  • 财政年份:
    2015
  • 资助金额:
    $ 3.35万
  • 项目类别:
    Discovery Grants Program - Individual
Approximation algorithms for NP-hard problems in network design
网络设计中NP难问题的近似算法
  • 批准号:
    138432-2009
  • 财政年份:
    2013
  • 资助金额:
    $ 3.35万
  • 项目类别:
    Discovery Grants Program - Individual
Approximation algorithms for NP-hard problems in network design
网络设计中NP难问题的近似算法
  • 批准号:
    138432-2009
  • 财政年份:
    2012
  • 资助金额:
    $ 3.35万
  • 项目类别:
    Discovery Grants Program - Individual

相似国自然基金

固定参数可解算法在平面图问题的应用以及和整数线性规划的关系
  • 批准号:
    60973026
  • 批准年份:
    2009
  • 资助金额:
    32.0 万元
  • 项目类别:
    面上项目
Computational Methods for Analyzing Toponome Data
  • 批准号:
    60601030
  • 批准年份:
    2006
  • 资助金额:
    17.0 万元
  • 项目类别:
    青年科学基金项目

相似海外基金

Approximation Algorithms for NP-Hard Problems
NP 困难问题的近似算法
  • 批准号:
    RGPIN-2019-04197
  • 财政年份:
    2022
  • 资助金额:
    $ 3.35万
  • 项目类别:
    Discovery Grants Program - Individual
Approximation Algorithms for NP-Hard Problems
NP 困难问题的近似算法
  • 批准号:
    RGPIN-2019-04197
  • 财政年份:
    2021
  • 资助金额:
    $ 3.35万
  • 项目类别:
    Discovery Grants Program - Individual
Approximation Algorithms for NP-Hard Problems
NP 困难问题的近似算法
  • 批准号:
    RGPIN-2019-04197
  • 财政年份:
    2020
  • 资助金额:
    $ 3.35万
  • 项目类别:
    Discovery Grants Program - Individual
Approximation Algorithms for NP-Hard Problems
NP 困难问题的近似算法
  • 批准号:
    RGPIN-2019-04197
  • 财政年份:
    2019
  • 资助金额:
    $ 3.35万
  • 项目类别:
    Discovery Grants Program - Individual
Approximation algorithms for NP-hard problems
NP 困难问题的近似算法
  • 批准号:
    RGPIN-2014-04351
  • 财政年份:
    2018
  • 资助金额:
    $ 3.35万
  • 项目类别:
    Discovery Grants Program - Individual
Approximation Algorithms for NP-hard Optimization Problems
NP 难优化问题的近似算法
  • 批准号:
    RGPIN-2014-06302
  • 财政年份:
    2018
  • 资助金额:
    $ 3.35万
  • 项目类别:
    Discovery Grants Program - Individual
Approximation algorithms for NP-hard problems
NP 困难问题的近似算法
  • 批准号:
    RGPIN-2014-04351
  • 财政年份:
    2017
  • 资助金额:
    $ 3.35万
  • 项目类别:
    Discovery Grants Program - Individual
Approximation Algorithms for NP-hard Optimization Problems
NP 难优化问题的近似算法
  • 批准号:
    RGPIN-2014-06302
  • 财政年份:
    2017
  • 资助金额:
    $ 3.35万
  • 项目类别:
    Discovery Grants Program - Individual
Approximation algorithms for NP-hard graph connectivity problems
NP 难图连通性问题的近似算法
  • 批准号:
    509110-2017
  • 财政年份:
    2017
  • 资助金额:
    $ 3.35万
  • 项目类别:
    University Undergraduate Student Research Awards
Approximation algorithms for NP-hard problems
NP 困难问题的近似算法
  • 批准号:
    RGPIN-2014-04351
  • 财政年份:
    2016
  • 资助金额:
    $ 3.35万
  • 项目类别:
    Discovery Grants Program - Individual
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了