ITR: Collaborative Research: Smoothed Analysis of Algorithms
ITR:协作研究:算法的平滑分析
基本信息
- 批准号:0707522
- 负责人:
- 金额:$ 38.18万
- 依托单位:
- 依托单位国家:美国
- 项目类别:Continuing Grant
- 财政年份:2006
- 资助国家:美国
- 起止时间:2006-08-01 至 2009-08-31
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
Graph partitioning is a fundamental combinatorial optimizationproblem that has many practical applications such asin supporting efficient load balancing for parallel processing,in VLSI layout, and in data clustering. This proposed research program focuses on the study of spectral methods for graph partitioning.Spectral methods make use of the eigenvectors of graph matrices (e.g., the Laplacian or the adjacency matrix of a graph) to construct a qualitypartitioning. They have been popularly used in practicefor partitioning meshes in scientific simulation, for dividing graphsderived from circuits, and for clustering data in web-graph analysisand information organization. However, the quality of the partition that these methods should produce has so far eluded precise analysis.Spielman and the PI made some breakthrough progresses.In particular, by proving that the second smallest eigenvalue ofthe Laplacian matrices of bounded-degree planar graphsis at most O(1/n), Spielman and the PIshowed that proper use of spectral techniques can producea bisection of graphs with cut size at most $O(\sqrt{n})$,which is best possible for the family of planar graphs.
图划分是一个基本的组合优化问题,有许多实际应用,如支持并行处理的有效负载平衡,VLSI布局和数据聚类。本研究计划的重点是研究图划分的谱方法。谱方法利用图矩阵的特征向量(例如,图的拉普拉斯矩阵或邻接矩阵)来构造一个质量分区。它们在实践中被广泛应用于科学模拟中的网格划分、电路图的划分以及网络图分析和信息组织中的数据聚类。然而,到目前为止,这些方法应该产生的分区的质量还没有得到精确的分析。斯皮尔曼和PI取得了一些突破性进展。特别是,通过证明有界度平面图的拉普拉斯矩阵的第二小特征值不超过O(1/n), Spielman等人证明了正确使用谱技术可以产生切尺寸不超过$O(\sqrt{n})$的图的平分,这是平面图族的最佳可能。
项目成果
期刊论文数量(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 }}
Daniel Spielman其他文献
35. Efficacy of Ketamine in Unmedicated Adults With OCD: A Randomized Controlled Trial
- DOI:
10.1016/j.biopsych.2023.02.218 - 发表时间:
2023-05-01 - 期刊:
- 影响因子:
- 作者:
Carolyn Rodriguez;Chi-Ming Chen;Gary Glover;Booil Jo;Daniel Spielman;Leanne Williams;Peter van Roessel;Charles DeBattista;Max Wintermark;Anthony Lombardi;Anthony Pinto;Keara Valentine;Maria Filippou-Frye;Jessica Hawkins;Elizabeth McCarthy;Pavithra Mukunda;Andrea Varias;Jordan Wilson;Brianna Wright - 通讯作者:
Brianna Wright
1.10 THALAMIC METABOLITE LEVELS AND SENSORY PROCESSING IN TWINS WITH AUTISM SPECTRUM DISORDER
- DOI:
10.1016/j.jaac.2016.09.011 - 发表时间:
2016-10-01 - 期刊:
- 影响因子:
- 作者:
John P. Hegarty;Meng Gu;Daniel Spielman;Sue Cleveland;Joachim J. Hallmayer;Laura C. Lazzeroni;Mira Raman;Julio Monterrey;Thomas Frazier;Jennifer M. Phillips;Allan L. Reiss;Antonio Hardan - 通讯作者:
Antonio Hardan
The power of adaptiveness and additional queries in random-self-reductions
- DOI:
10.1007/bf01202287 - 发表时间:
1994-06-01 - 期刊:
- 影响因子:1.000
- 作者:
Joan Feigenbaum;Lance Fortnow;Carsten Lund;Daniel Spielman - 通讯作者:
Daniel Spielman
310. Simultaneous [18F]Flumazenil-Positron Emission Tomography and GABA-Magnetic Resonance Spectroscopy in Adults with Autism and Healthy Volunteers
- DOI:
10.1016/j.biopsych.2017.02.325 - 发表时间:
2017-05-15 - 期刊:
- 影响因子:
- 作者:
Lawrence Fung;Ryan Flores;Meng Gu;Trine Hjoernevik;Antonio Hardan;Daniel Spielman;Frederick Chin - 通讯作者:
Frederick Chin
508 - Proton specfroscopy reveals normal naa concentration in cortical gray mastter in schizophrenic patients
- DOI:
10.1016/s0920-9964(97)82516-9 - 发表时间:
1997-01-01 - 期刊:
- 影响因子:
- 作者:
Kelvin O. Lim;Elfar Adalsteinsson;Daniel Spielman;Edith V. Sullivan;Adolf Pfefferbaum - 通讯作者:
Adolf Pfefferbaum
Daniel Spielman的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Daniel Spielman', 18)}}的其他基金
AF: Medium: Generalized Algebraic Graph Theory: Algorithms and Analysis
AF:中:广义代数图论:算法与分析
- 批准号:
1562041 - 财政年份:2016
- 资助金额:
$ 38.18万 - 项目类别:
Continuing Grant
AF: Large: Collaborative Research: Algebraic Graph Algorithms: The Laplacian and Beyond
AF:大型:协作研究:代数图算法:拉普拉斯算子及其他算法
- 批准号:
1111257 - 财政年份:2011
- 资助金额:
$ 38.18万 - 项目类别:
Standard Grant
AF: Small: Spectral Graph Theory, Point Clouds, and Linear Equation Solvers
AF:小:谱图理论、点云和线性方程求解器
- 批准号:
0915487 - 财政年份:2009
- 资助金额:
$ 38.18万 - 项目类别:
Standard Grant
Collaborative Research: Spectral Graph Theory and Its Applications
合作研究:谱图理论及其应用
- 批准号:
0634957 - 财政年份:2007
- 资助金额:
$ 38.18万 - 项目类别:
Continuing Grant
Spectral Methods: Algorithms and Applications
谱方法:算法和应用
- 批准号:
0634904 - 财政年份:2006
- 资助金额:
$ 38.18万 - 项目类别:
Standard Grant
ITR: Collaborative Research: Smoothed Analysis of Algorithms
ITR:协作研究:算法的平滑分析
- 批准号:
0324914 - 财政年份:2003
- 资助金额:
$ 38.18万 - 项目类别:
Continuing Grant
ITR/SY(CISE): Why algorithms work well in practice: pertubation-based average-case analysis of the simplex algorithm and beyond
ITR/SY(CISE):为什么算法在实践中表现良好:单纯形算法及其他算法的基于扰动的平均情况分析
- 批准号:
0112487 - 财政年份:2001
- 资助金额:
$ 38.18万 - 项目类别:
Standard Grant
CAREER: Computationally Efficient Error-Correcting Codes and Their Applications
职业:计算高效的纠错码及其应用
- 批准号:
9701304 - 财政年份:1997
- 资助金额:
$ 38.18万 - 项目类别:
Continuing Grant
Mathematical Sciences Postdoctoral Research Fellowships
数学科学博士后研究奖学金
- 批准号:
9508950 - 财政年份:1995
- 资助金额:
$ 38.18万 - 项目类别:
Fellowship Award
相似海外基金
ITR Collaborative Research: Pervasively Secure Infrastructures (PSI): Integrating Smart Sensing, Data Mining, Pervasive Networking, and Community Computing
ITR 协作研究:普遍安全基础设施 (PSI):集成智能传感、数据挖掘、普遍网络和社区计算
- 批准号:
1404694 - 财政年份:2013
- 资助金额:
$ 38.18万 - 项目类别:
Continuing Grant
ITR-SCOTUS: A Resource for Collaborative Research in Speech Technology, Linguistics, Decision Processes, and the Law
ITR-SCOTUS:语音技术、语言学、决策过程和法律合作研究的资源
- 批准号:
1139735 - 财政年份:2011
- 资助金额:
$ 38.18万 - 项目类别:
Continuing Grant
ITR/NGS: Collaborative Research: DDDAS: Data Dynamic Simulation for Disaster Management
ITR/NGS:合作研究:DDDAS:灾害管理数据动态模拟
- 批准号:
0963973 - 财政年份:2009
- 资助金额:
$ 38.18万 - 项目类别:
Continuing Grant
ITR/NGS: Collaborative Research: DDDAS: Data Dynamic Simulation for Disaster Management
ITR/NGS:合作研究:DDDAS:灾害管理数据动态模拟
- 批准号:
1018072 - 财政年份:2009
- 资助金额:
$ 38.18万 - 项目类别:
Continuing Grant
ITR Collaborative Research: A Reusable, Extensible, Optimizing Back End
ITR 协作研究:可重用、可扩展、优化的后端
- 批准号:
0838899 - 财政年份:2008
- 资助金额:
$ 38.18万 - 项目类别:
Continuing Grant
ITR Collaborative Research: Pervasively Secure Infrastructures (PSI): Integrating Smart Sensing, Data Mining, Pervasive Networking, and Community Computing
ITR 协作研究:普遍安全基础设施 (PSI):集成智能传感、数据挖掘、普遍网络和社区计算
- 批准号:
0833849 - 财政年份:2008
- 资助金额:
$ 38.18万 - 项目类别:
Continuing Grant
ITR/NGS: Collaborative Research: DDDAS: Data Dynamic Simulation for Disaster Management
ITR/NGS:合作研究:DDDAS:灾害管理数据动态模拟
- 批准号:
0808419 - 财政年份:2007
- 资助金额:
$ 38.18万 - 项目类别:
Continuing Grant
ITR: Collaborative Research: Modeling and Display of Haptic Information for Enhanced Performance of Computer-Integrated Surgery
ITR:协作研究:触觉信息建模和显示,以提高计算机集成手术的性能
- 批准号:
0711040 - 财政年份:2007
- 资助金额:
$ 38.18万 - 项目类别:
Standard Grant
ITR: Collaborative Research - ASE - (sim+dmc): Image-based Biophysical Modeling: Scalable Registration and Inversion Algorithms and Distributed Computing
ITR:协作研究 - ASE - (sim dmc):基于图像的生物物理建模:可扩展配准和反演算法以及分布式计算
- 批准号:
0849301 - 财政年份:2007
- 资助金额:
$ 38.18万 - 项目类别:
Continuing Grant
Collaborative Research: ITR-(ASE)-(dmc): Overcoming Fractionation Errors in Cancer Treatement Planning
合作研究:ITR-(ASE)-(dmc):克服癌症治疗计划中的分割错误
- 批准号:
0749671 - 财政年份:2006
- 资助金额:
$ 38.18万 - 项目类别:
Standard Grant