ITR: Collaborative Research: Smoothed Analysis of Algorithms
ITR:协作研究:算法的平滑分析
基本信息
- 批准号:0324914
- 负责人:
- 金额:$ 50万
- 依托单位:
- 依托单位国家:美国
- 项目类别:Continuing Grant
- 财政年份:2003
- 资助国家:美国
- 起止时间:2003-09-01 至 2007-01-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),斯皮尔曼和PI表明,正确使用谱技术可以产生最多具有切割尺寸的图的二分 $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
- 资助金额:
$ 50万 - 项目类别:
Continuing Grant
AF: Large: Collaborative Research: Algebraic Graph Algorithms: The Laplacian and Beyond
AF:大型:协作研究:代数图算法:拉普拉斯算子及其他算法
- 批准号:
1111257 - 财政年份:2011
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
AF: Small: Spectral Graph Theory, Point Clouds, and Linear Equation Solvers
AF:小:谱图理论、点云和线性方程求解器
- 批准号:
0915487 - 财政年份:2009
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
Collaborative Research: Spectral Graph Theory and Its Applications
合作研究:谱图理论及其应用
- 批准号:
0634957 - 财政年份:2007
- 资助金额:
$ 50万 - 项目类别:
Continuing Grant
Spectral Methods: Algorithms and Applications
谱方法:算法和应用
- 批准号:
0634904 - 财政年份:2006
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
ITR: Collaborative Research: Smoothed Analysis of Algorithms
ITR:协作研究:算法的平滑分析
- 批准号:
0707522 - 财政年份:2006
- 资助金额:
$ 50万 - 项目类别:
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
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
CAREER: Computationally Efficient Error-Correcting Codes and Their Applications
职业:计算高效的纠错码及其应用
- 批准号:
9701304 - 财政年份:1997
- 资助金额:
$ 50万 - 项目类别:
Continuing Grant
Mathematical Sciences Postdoctoral Research Fellowships
数学科学博士后研究奖学金
- 批准号:
9508950 - 财政年份:1995
- 资助金额:
$ 50万 - 项目类别:
Fellowship Award
相似海外基金
ITR Collaborative Research: Pervasively Secure Infrastructures (PSI): Integrating Smart Sensing, Data Mining, Pervasive Networking, and Community Computing
ITR 协作研究:普遍安全基础设施 (PSI):集成智能传感、数据挖掘、普遍网络和社区计算
- 批准号:
1404694 - 财政年份:2013
- 资助金额:
$ 50万 - 项目类别:
Continuing Grant
ITR-SCOTUS: A Resource for Collaborative Research in Speech Technology, Linguistics, Decision Processes, and the Law
ITR-SCOTUS:语音技术、语言学、决策过程和法律合作研究的资源
- 批准号:
1139735 - 财政年份:2011
- 资助金额:
$ 50万 - 项目类别:
Continuing Grant
ITR/NGS: Collaborative Research: DDDAS: Data Dynamic Simulation for Disaster Management
ITR/NGS:合作研究:DDDAS:灾害管理数据动态模拟
- 批准号:
0963973 - 财政年份:2009
- 资助金额:
$ 50万 - 项目类别:
Continuing Grant
ITR/NGS: Collaborative Research: DDDAS: Data Dynamic Simulation for Disaster Management
ITR/NGS:合作研究:DDDAS:灾害管理数据动态模拟
- 批准号:
1018072 - 财政年份:2009
- 资助金额:
$ 50万 - 项目类别:
Continuing Grant
ITR Collaborative Research: A Reusable, Extensible, Optimizing Back End
ITR 协作研究:可重用、可扩展、优化的后端
- 批准号:
0838899 - 财政年份:2008
- 资助金额:
$ 50万 - 项目类别:
Continuing Grant
ITR Collaborative Research: Pervasively Secure Infrastructures (PSI): Integrating Smart Sensing, Data Mining, Pervasive Networking, and Community Computing
ITR 协作研究:普遍安全基础设施 (PSI):集成智能传感、数据挖掘、普遍网络和社区计算
- 批准号:
0833849 - 财政年份:2008
- 资助金额:
$ 50万 - 项目类别:
Continuing Grant
ITR/NGS: Collaborative Research: DDDAS: Data Dynamic Simulation for Disaster Management
ITR/NGS:合作研究:DDDAS:灾害管理数据动态模拟
- 批准号:
0808419 - 财政年份:2007
- 资助金额:
$ 50万 - 项目类别:
Continuing 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
- 资助金额:
$ 50万 - 项目类别:
Continuing Grant
ITR: Collaborative Research: Modeling and Display of Haptic Information for Enhanced Performance of Computer-Integrated Surgery
ITR:协作研究:触觉信息建模和显示,以提高计算机集成手术的性能
- 批准号:
0711040 - 财政年份:2007
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
ITR Collaborative Research: GEON: A Research Project to Create Cyberinfrastructure for the Geosciences
ITR 合作研究:GEON:为地球科学创建网络基础设施的研究项目
- 批准号:
0724265 - 财政年份:2006
- 资助金额:
$ 50万 - 项目类别:
Continuing Grant