Approximation Algorithms for NP-Hard Problems
NP 困难问题的近似算法
基本信息
- 批准号:RGPIN-2019-04197
- 负责人:
- 金额:$ 3.5万
- 依托单位:
- 依托单位国家:加拿大
- 项目类别:Discovery Grants Program - Individual
- 财政年份:2019
- 资助国家:加拿大
- 起止时间:2019-01-01 至 2020-12-31
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
Network design, network flows, and graph connectivity are core topics in Theoretical Computer Science, Operations Research, and Combinatorial Optimization. Important algorithmic and structural 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, congestion control for road traffic, and the analysis of social networks. 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.******In the design and analysis of approximation algorithms, I am using methods such as: algorithms and theory from combinatorial optimization (in particular, matchings and network flows), rounding of linear-programming relaxations, the primal-dual method, lift-and-project methods, and dynamic programming.******I plan to attack some outstanding open questions in network design jointly with my graduate students and co-authors, building on my recent major advances and journal publications.******Three key modules of my research program are summarized below.******(A) Network Design for Node-Connectivity Requirements******A basic problem in network design, called the NC-SNDP, is to find a minimum-cost sub-network H of a given network G such that H satisfies some prespecified NODE-connectivity requirements. I am attacking (with my grad students) a fundamental open problem: design an approximation algorithm for NC-SNDP whose guarantee is independent of the number of nodes/edges/terminals of the network G.******(B) Thin trees and the Traveling Salesman Problem (TSP)******The thinness parameter of a spanning tree T is the maximum over all cuts of the proportion of the edges of T in the cut. Goddyn conjectured that for any required thinness, a graph of sufficiently large edge-connectivity has a spanning tree with that thinness. An algorithmic (poly-time) proof would give major advances on approximation algorithms for ATSP. My long-term goal is such a proof. I am designing (with my grad students) efficient algorithms for finding thin spanning trees in special classes of graphs.******(C) Lift-and-Project Systems for Combinatorial Optimization******A key open question in the area is to improve on the approximation guarantee of two for the minimum-cost 2-edge connected spanning subgraph (2-ECSS) problem. My immediate goal is to derive an approximation guarantee better than two for a special case of this problem called the Forest Augmentation Problem (FAP) relative to a relaxation of FAP obtained via Lift-and-Project methods. This will generalize results that I have published with Gao (my completed Ph.D. student).**
网络设计、网络流和图连接性是理论计算机科学、运筹学和组合优化的核心主题。重要的算法和结构范例是在这些主题的背景下发展起来的,例如最小生成树的贪婪算法和网络流的最大流最小割定理。此外,这些主题出现在许多实际情况下,如容错通信网络的设计,道路交通的拥塞控制,以及社交网络的分析。在实际应用中,许多问题都是NP难的。这意味着最优解决方案不能在合理的运行时间内计算,以P. NP猜想因此,研究集中在近似算法上,即,高效算法,找到在最优解的保证因子内的解决方案。******在近似算法的设计和分析中,我使用的方法包括:组合优化的算法和理论(特别是匹配和网络流),线性规划松弛的舍入,原始对偶方法,提升和投影方法和动态规划。我计划与我的研究生和合作者一起解决网络设计中一些悬而未决的问题,建立在我最近的主要进展和期刊出版物的基础上。我的研究计划的三个关键模块总结如下。* (A)网络设计中的一个基本问题,称为NC-SNDP,是找到给定网络G的最小成本子网H,使得H满足某些预先指定的节点连接要求。我正在(与我的研究生一起)解决一个基本的开放问题:设计NC-SNDP的近似算法,其保证独立于网络G的节点/边/终端的数量。* (B)稀疏树和旅行商问题(TSP)** 生成树T的稀疏度参数是T的边在割中的比例在所有割上的最大值。 Goddyn指出,对于任何所需的稀疏度,一个足够大的边连通度的图都有一个具有该稀疏度的生成树。一个算法(多时间)的证明将使ATSP的近似算法取得重大进展。我的长期目标就是这样的证明。我正在设计(与我的研究生)有效的算法,用于在特殊的图类中找到薄生成树。(C)提升和投影系统的组合优化 ** 在该领域的一个关键的开放问题是改善的近似保证2的最小成本2-边连接生成子图(2-ECSS)问题。我的直接目标是得到一个近似保证优于两个这个问题的一个特殊情况下,称为森林扩增问题(FAP)相对于通过提升和项目方法获得的FAP放松。这将推广我和高(我完成的博士学位)一起发表的结果。学生)。**
项目成果
期刊论文数量(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.5万 - 项目类别:
Discovery Grants Program - Individual
Approximation Algorithms for NP-Hard Problems
NP 困难问题的近似算法
- 批准号:
RGPIN-2019-04197 - 财政年份:2021
- 资助金额:
$ 3.5万 - 项目类别:
Discovery Grants Program - Individual
Approximation Algorithms for NP-Hard Problems
NP 困难问题的近似算法
- 批准号:
RGPIN-2019-04197 - 财政年份:2020
- 资助金额:
$ 3.5万 - 项目类别:
Discovery Grants Program - Individual
Approximation algorithms for NP-hard problems
NP 困难问题的近似算法
- 批准号:
RGPIN-2014-04351 - 财政年份:2018
- 资助金额:
$ 3.5万 - 项目类别:
Discovery Grants Program - Individual
Approximation algorithms for NP-hard problems
NP 困难问题的近似算法
- 批准号:
RGPIN-2014-04351 - 财政年份:2017
- 资助金额:
$ 3.5万 - 项目类别:
Discovery Grants Program - Individual
Approximation algorithms for NP-hard problems
NP 困难问题的近似算法
- 批准号:
RGPIN-2014-04351 - 财政年份:2016
- 资助金额:
$ 3.5万 - 项目类别:
Discovery Grants Program - Individual
Approximation algorithms for NP-hard problems
NP 困难问题的近似算法
- 批准号:
RGPIN-2014-04351 - 财政年份:2015
- 资助金额:
$ 3.5万 - 项目类别:
Discovery Grants Program - Individual
Approximation algorithms for NP-hard problems
NP 困难问题的近似算法
- 批准号:
RGPIN-2014-04351 - 财政年份:2014
- 资助金额:
$ 3.5万 - 项目类别:
Discovery Grants Program - Individual
Approximation algorithms for NP-hard problems in network design
网络设计中NP难问题的近似算法
- 批准号:
138432-2009 - 财政年份:2013
- 资助金额:
$ 3.5万 - 项目类别:
Discovery Grants Program - Individual
Approximation algorithms for NP-hard problems in network design
网络设计中NP难问题的近似算法
- 批准号:
138432-2009 - 财政年份:2012
- 资助金额:
$ 3.5万 - 项目类别:
Discovery Grants Program - Individual
相似海外基金
Approximation Algorithms for NP-Hard Problems
NP 困难问题的近似算法
- 批准号:
RGPIN-2019-04197 - 财政年份:2022
- 资助金额:
$ 3.5万 - 项目类别:
Discovery Grants Program - Individual
Approximation Algorithms for NP-Hard Problems
NP 困难问题的近似算法
- 批准号:
RGPIN-2019-04197 - 财政年份:2021
- 资助金额:
$ 3.5万 - 项目类别:
Discovery Grants Program - Individual
Approximation Algorithms for NP-Hard Problems
NP 困难问题的近似算法
- 批准号:
RGPIN-2019-04197 - 财政年份:2020
- 资助金额:
$ 3.5万 - 项目类别:
Discovery Grants Program - Individual
Approximation algorithms for NP-hard problems
NP 困难问题的近似算法
- 批准号:
RGPIN-2014-04351 - 财政年份:2018
- 资助金额:
$ 3.5万 - 项目类别:
Discovery Grants Program - Individual
Approximation Algorithms for NP-hard Optimization Problems
NP 难优化问题的近似算法
- 批准号:
RGPIN-2014-06302 - 财政年份:2018
- 资助金额:
$ 3.5万 - 项目类别:
Discovery Grants Program - Individual
Approximation algorithms for NP-hard problems
NP 困难问题的近似算法
- 批准号:
RGPIN-2014-04351 - 财政年份:2017
- 资助金额:
$ 3.5万 - 项目类别:
Discovery Grants Program - Individual
Approximation Algorithms for NP-hard Optimization Problems
NP 难优化问题的近似算法
- 批准号:
RGPIN-2014-06302 - 财政年份:2017
- 资助金额:
$ 3.5万 - 项目类别:
Discovery Grants Program - Individual
Approximation algorithms for NP-hard graph connectivity problems
NP 难图连通性问题的近似算法
- 批准号:
509110-2017 - 财政年份:2017
- 资助金额:
$ 3.5万 - 项目类别:
University Undergraduate Student Research Awards
Approximation algorithms for NP-hard problems
NP 困难问题的近似算法
- 批准号:
RGPIN-2014-04351 - 财政年份:2016
- 资助金额:
$ 3.5万 - 项目类别:
Discovery Grants Program - Individual
Approximation Algorithms for NP-hard Optimization Problems
NP 难优化问题的近似算法
- 批准号:
RGPIN-2014-06302 - 财政年份:2016
- 资助金额:
$ 3.5万 - 项目类别:
Discovery Grants Program - Individual