课题基金 / 基金详情

AF: Small: Graph Partitioning and Spectral Methods

AF: Small: Graph Partitioning and Spectral Methods
AF:小:图划分和谱方法
批准号:
1540685
负责人:
Luca Trevisan
金额:
$28.97万
依托单位国家:
美国
项目类别:
Standard Grant
财政年份:
2014
资助国家:
美国
项目状态:
已结题
起止时间:
2014-07-01 至 2017-09-30

项目摘要

项目成果

Luca Trevisan的其他基金

相似基金

相关文献

中文摘要
翻译
基于谱技术的算法往往是快速的,并且具有简单而优雅的结构;它们的分析有助于解释实践中采用的相关启发式的经验上的良好性能;并且它们的分析经常揭示代数和组合图不变量之间的有用的数学关系,这可以在算法设计之外具有有用的应用。这项由这笔拨款支持的研究探索了切割和聚类问题的新算法,流行的谱聚类启发式的严格理由,以及图的谱轮廓与其组合属性之间的各种关系。PI和他的合作者将研究图的拉普拉斯矩阵的多个特征向量在聚类算法设计中的使用,他们将提供基于多个特征向量的聚类启发式的严格分析,并将探索特征值接近重数的组合特征。在图划分算法的设计中,将探索使用随机游动和其他概率过程的新方法。PI正在撰写一本关于最稀疏割近似算法、扩展图的构造和图中随机游动分析这三个相关主题的专著。这三个主题在数学上密切相关,但它们在很大程度上是由不同的社区追求的;这本专著将强调这种联系,并鼓励这三个领域中的每一个领域的研究人员在其他领域进行研究。
英文摘要
Algorithms based on spectral techniques tend to be fast and to have a simple and elegant structure; their analysis helps explain the empirically good performance of related heuristics that are adopted in practice; and their analysis often uncovers useful mathematical relationships between algebraic and combinatorial graph invariants, which can have useful applications outside of algorithm design. The research supported by this grant explores new algorithms for cut and clustering problems, rigorous justifications for popular spectral clustering heuristics, and various relationships between the spectral profile of a graph and its combinatorial properties. The PI and his collaborators will study the use of multiple eigenvectors of the Laplacian matrix of a graph in the design of clustering algorithms, they will provide rigorous analyses of clustering heuristics based on multiple eigenvectors, and will explore combinatorial characterizations of eigenvalue near-multiplicities. New approaches to the use of random walks and other probabilistic processes will be explored in the design of graph partitioning algorithms.The PI is working on a monograph on the three related themes of sparsest cut approximation algorithms, constructions of expander graphs, and analysis of random walks in graphs. The three topics are closely related mathematically, but they are pursued by largely distinct community; the monograph will emphasize the connection and encourage researchers in each of the three areas to pursue research in the others.
期刊论文(0)
专著(0)
科研奖励(0)
会议论文
AF: Small: Spectral and SDP Techniques: Average-Case Analysis and Subexponential Algorithms
  • 批准号:
    1815434
  • 项目类别:
    Standard Grant
  • 资助金额:
    $50.0万
  • 财政年份:
    2018
  • 负责人:
    Luca Trevisan
  • 依托单位:
EAGER: New Graph and CSP Algorithms Based on Spectral and SDP Techniques
  • 批准号:
    1655215
  • 项目类别:
    Standard Grant
  • 资助金额:
    $10.0万
  • 财政年份:
    2016
  • 负责人:
    Luca Trevisan
  • 依托单位:
AF: Small: Graph Partitioning and Spectral Methods
  • 批准号:
    1216642
  • 项目类别:
    Standard Grant
  • 资助金额:
    $40.0万
  • 财政年份:
    2012
  • 负责人:
    Luca Trevisan
  • 依托单位:
AF: Small: Unconditional Lower Bounds in Approximability and Cryptography
  • 批准号:
    1161812
  • 项目类别:
    Continuing Grant
  • 资助金额:
    $39.25万
  • 财政年份:
    2011
  • 负责人:
    Luca Trevisan
  • 依托单位:
国内基金
海外基金
昼夜节律性small RNA在血斑形成时间推断中的法医学应用研究
  • 批准号:
  • 项目类别:
    省市级项目
  • 资助金额:
    --
  • 批准年份:
    2024
  • 负责人:
  • 依托单位:
tRNA-derived small RNA上调YBX1/CCL5通路参与硼替佐米诱导慢性疼痛的机制研究
  • 批准号:
  • 项目类别:
    省市级项目
  • 资助金额:
    10.0万元
  • 批准年份:
    2022
  • 负责人:
    张祥忠
  • 依托单位:
Small RNA调控I-F型CRISPR-Cas适应性免疫性的应答及分子机制
Small RNAs调控解淀粉芽胞杆菌FZB42生防功能的机制研究
  • 批准号:
    31972324
  • 项目类别:
    面上项目
  • 资助金额:
    58.0万元
  • 批准年份:
    2019
  • 负责人:
    高学文
  • 依托单位: