Collaborative Research: AF: Medium: Fast Combinatorial Algorithms for (Dynamic) Matchings and Shortest Paths
合作研究:AF:中:(动态)匹配和最短路径的快速组合算法
基本信息
- 批准号:2402284
- 负责人:
- 金额:$ 59.94万
- 依托单位:
- 依托单位国家:美国
- 项目类别:Continuing Grant
- 财政年份:2024
- 资助国家:美国
- 起止时间:2024-07-01 至 2028-06-30
- 项目状态:未结题
- 来源:
- 关键词:
项目摘要
A graph is a collection of vertices (points or objects), and a collection of edges (links or lines), that connect pairs of vertices. Graphs are a central and an extensively studied type of mathematical object, and they are commonly used to model various problems in many different real world scenarios and applications. For example, it is natural to model a road network in a city, or a computer network, or friendship relationships in a social network as a graph. There are countless other scenarios where a problem one needs to solve, or an object one desires to study, can be naturally abstracted by a graph. As a consequence, the design of efficient algorithms for central graph problems is fundamental to computer science and beyond, and has a significant impact on many aspects of computation. As the amount of data that applications need to deal with grows, it is increasingly important to ensure that such algorithms are very fast. In this project, the investigators will study several central graph problems, such as Maximum Matching, Maximum Flow, and Shortest Paths, in two basic settings. The first is the standard model where the input graph is known in advance, and the goal is to design a fast algorithm for the problem, with running time not significantly higher than the time required to read the input, which is close to the fastest possible running time. The second is the model of dynamic algorithms, where the graph changes over time (for example, consider a road network, where the computation has to account for roads becoming more or less congested with traffic), and the goal is to quickly support queries about the graph, such as, for example, computing a short path between two given vertices. This project is organized along four main interconnected thrusts. The first thrust focuses on the design of algorithms for dynamic All-Pairs Shortest Paths (APSP), that can withstand an adaptive adversary, and that significantly improve upon the currently known tradeoffs between the approximation quality and the running time, in both directed and undirected graphs. Algorithms for APSP and its variants are often used in combination with the Multiplicative Weights Update framework to efficiently solve various flow and cut problems in graphs, and thus provide a valuable and powerful algorithmic toolkit. The second thrust is directed towards improving and extending known expander-related tools that are often used in the design of fast algorithms for various graph problems. Expanders are playing an increasingly central role in graph algorithms, and these tools can serve as building blocks for many other graph problems. The third thrust focuses on the Maximum Matching problem. Using techniques inspired by algorithms for dynamic shortest path in directed graphs, the goal of this part of the project is to develop fast combinatorial algorithms for both the bipartite and the general version of the problem. The final thrust focuses on designing improved algorithms for maintaining near-optimal matchings in dynamic graphs, building on insights and algorithms developed for the second and the third thrusts.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.
图是顶点(点或对象)和连接顶点对的边(链接或线)的集合。图是数学对象的核心和广泛研究的类型,它们通常用于在许多不同的现实世界场景和应用程序中建模各种问题。例如,将城市中的道路网络或计算机网络或社交网络中的友谊关系建模为图形是很自然的。在无数其他场景中,一个需要解决的问题,或者一个想要研究的对象,都可以用图形自然地抽象出来。因此,为中心图问题设计有效的算法是计算机科学乃至其他领域的基础,并对计算的许多方面产生重大影响。随着应用程序需要处理的数据量的增长,确保这些算法非常快变得越来越重要。在这个项目中,研究者将在两个基本设置中研究几个中心图问题,如最大匹配、最大流量和最短路径。第一种是预先知道输入图的标准模型,其目标是为问题设计一个快速的算法,其运行时间不会显著高于读取输入所需的时间,这接近于最快的可能运行时间。第二种是动态算法模型,其中图随着时间的推移而变化(例如,考虑一个道路网络,其中计算必须考虑到道路或多或少因交通拥堵而变得拥挤),其目标是快速支持关于图的查询,例如,计算两个给定顶点之间的短路径。该项目由四个主要的相互关联的重点组成。第一个重点是动态全对最短路径(APSP)算法的设计,它可以承受自适应对手,并且在有向图和无向图中显著改善了目前已知的近似质量和运行时间之间的权衡。APSP及其变体算法通常与乘法加权更新框架结合使用,以有效地解决图中的各种流和切问题,从而提供了一个有价值且功能强大的算法工具包。第二个重点是改进和扩展已知的扩展器相关工具,这些工具通常用于设计各种图形问题的快速算法。扩展器在图算法中扮演着越来越重要的角色,这些工具可以作为许多其他图问题的构建块。第三个重点是最大匹配问题。利用受有向图中动态最短路径算法启发的技术,这部分项目的目标是为问题的二部和一般版本开发快速组合算法。最后一个重点是设计改进的算法,以维护动态图中接近最优的匹配,建立在第二和第三个重点的见解和算法的基础上。该奖项反映了美国国家科学基金会的法定使命,并通过使用基金会的知识价值和更广泛的影响审查标准进行评估,被认为值得支持。
项目成果
期刊论文数量(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 }}
Sanjeev Khanna其他文献
Maximum Bipartite Matching in ?2+?(1) Time via a Combinatorial Algorithm
通过组合算法在 ?2+?(1) 时间内实现最大二分匹配
- DOI:
- 发表时间:
2024 - 期刊:
- 影响因子:0
- 作者:
Julia Chuzhoy;Sanjeev Khanna - 通讯作者:
Sanjeev Khanna
Palette Sparsification Beyond (∆ + 1) Vertex 1 Coloring 2
调色板稀疏化超出 (Δ + 1) 顶点 1 着色 2
- DOI:
- 发表时间:
2020 - 期刊:
- 影响因子:0
- 作者:
Noga Alon;Sepehr Assadi;Suman Bera;Amit Chakrabarti;Prantar Ghosh;Guru Guruganesh;David Harris;Sanjeev Khanna;Hsin - 通讯作者:
Hsin
Theory of Computing
计算理论
- DOI:
10.4086/toc - 发表时间:
2013 - 期刊:
- 影响因子:0
- 作者:
Alexandr Andoni;Nikhil Bansal;P. Beame;Giuseppe Italiano;Sanjeev Khanna;Ryan O’Donnell;T. Pitassi;T. Rabin;Tim Roughgarden;Clifford Stein;Rocco Servedio;Amir Abboud;Nima Anari;Ibm Srinivasan Arunachalam;T. J. Watson;Research Center;Petra Berenbrink;Aaron Bernstein;Aditya Bhaskara;Sayan Bhattacharya;Eric Blais;H. Bodlaender;Adam Bouland;Anne Broadbent;Mark Bun;Timothy Chan;Arkadev Chattopadhyay;Xue Chen;Gil Cohen;Dana Dachman;Anindya De;Shahar Dobzhinski;Zhiyi Huang;Ken;Robin Kothari;Marvin Künnemann;Tu Kaiserslautern;Rasmus Kyng;E. Zurich;Sophie Laplante;D. Lokshtanov;S. Mahabadi;Nicole Megow;Ankur Moitra;Technion Shay Moran;Google Research;Christopher Musco;Prasad Raghavendra;Alex Russell;Laura Sanità;Alex Slivkins;David Steurer;Epfl Ola Svensson;Chaitanya Swamy;Madhur Tulsiani;Christos Tzamos;Andreas Wiese;Mary Wootters;Huacheng Yu;Aaron Potechin;Aaron Sidford;Aarushi Goel;Aayush Jain;Abhiram Natarajan;Abhishek Shetty;Adam Karczmarz;Adam O’Neill;Aditi Dudeja;Aditi Laddha;Aditya Krishnan;Adrian Vladu Afrouz;J. Ameli;Ainesh Bakshi;Akihito Soeda;Akshay Krishnamurthy;Albert Cheu;A. Grilo;Alex Wein;Alexander Belov;Alexander Block;Alexander Golovnev;Alexander Poremba;Alexander Shen;Alexander Skopalik;Alexandra Henzinger;Alexandros Hollender;Ali Parviz;Alkis Kalavasis;Allen Liu;Aloni Cohen;Amartya Shankha;Biswas Amey;Bhangale Amin;Coja;Yehudayoff Amir;Zandieh Amit;Daniely Amit;Kumar Amnon;Ta;Beimel Anand;Louis Anand Natarajan;Anders Claesson;André Chailloux;André Nusser;Andrea Coladangelo;Andrea Lincoln;Andreas Björklund;Andreas Maggiori;A. Krokhin;A. Romashchenko;Andrej Risteski;Anirban Chowdhury;Anirudh Krishna;A. Mukherjee;Ankit Garg;Anna Karlin;Anthony Leverrier;Antonio Blanca;A. Antoniadis;Anupam Gupta;Anupam Prakash;A. Singh;Aravindan Vijayaraghavan;Argyrios Deligkas;Ariel Kulik;Ariel Schvartzman;Ariel Shaulker;A. Cornelissen;Arka Rai;Choudhuri Arkady;Yerukhimovich Arnab;Bhattacharyya Arthur Mehta;Artur Czumaj;A. Backurs;A. Jambulapati;Ashley Montanaro;A. Sah;A. Mantri;Aviad Rubinstein;Avishay Tal;Badih Ghazi;Bartek Blaszczyszyn;Benjamin Moseley;Benny Pinkas;Bento Natura;Bernhard Haeupler;Bill Fefferman;B. Mance;Binghui Peng;Bingkai Lin;B. Sinaimeri;Bo Waggoner;Bodo Manthey;Bohdan Kivva;Brendan Lucier Bundit;Laekhanukit Burak;Sahinoglu Cameron;Seth Chaodong Zheng;Charles Carlson;Chen;Chenghao Guo;Chenglin Fan;Chenwei Wu;Chethan Kamath;Chi Jin;J. Thaler;Jyun;Kaave Hosseini;Kaito Fujii;Kamesh Munagala;Kangning Wang;Kanstantsin Pashkovich;Karl Bringmann Karol;Wegrzycki Karteek;Sreenivasaiah Karthik;Chandrasekaran Karthik;Sankararaman Karthik;C. S. K. Green;Larsen Kasturi;Varadarajan Keita;Xagawa Kent Quanrud;Kevin Schewior;Kevin Tian;Kilian Risse;Kirankumar Shiragur;K. Pruhs;K. Efremenko;Konstantin Makarychev;Konstantin Zabarnyi;Krišj¯anis Pr¯usis;Kuan Cheng;Kuikui Liu;Kunal Marwaha;Lars Rohwedder László;Kozma László;A. Végh;L'eo Colisson;Leo de Castro;Leonid Barenboim Letong;Li;Li;L. Roditty;Lieven De;Lathauwer Lijie;Chen Lior;Eldar Lior;Rotem Luca Zanetti;Luisa Sinisclachi;Luke Postle;Luowen Qian;Lydia Zakynthinou;Mahbod Majid;Makrand Sinha;Malin Rau Manas;Jyoti Kashyop;Manolis Zampetakis;Maoyuan Song;Marc Roth;Marc Vinyals;Marcin Bieńkowski;Marcin Pilipczuk;Marco Molinaro;Marcus Michelen;Mark de Berg;M. Jerrum;Mark Sellke;Mark Zhandry;Markus Bläser;Markus Lohrey;Marshall Ball;Marthe Bonamy;Martin Fürer;Martin Hoefer;M. Kokainis;Masahiro Hachimori;Matteo Castiglioni;Matthias Englert;Matti Karppa;Max Hahn;Max Hopkins;Maximilian Probst;Gutenberg Mayank Goswami;Mehtaab Sawhney;Meike Hatzel;Meng He;Mengxiao Zhang;Meni Sadigurski;M. Parter;M. Dinitz;Michael Elkin;Michael Kapralov;Michael Kearns;James R. Lee;Sudatta Bhattacharya;Michal Koucký;Hadley Black;Deeparnab Chakrabarty;C. Seshadhri;Mahsa Derakhshan;Naveen Durvasula;Nika Haghtalab;Peter Kiss;Thatchaphol Saranurak;Soheil Behnezhad;M. Roghani;Hung Le;Shay Solomon;Václav Rozhon;Anders Martinsson;Christoph Grunau;G. Z. —. Eth;Zurich;Switzerland;Morris Yau — Massachusetts;Noah Golowich;Dhruv Rohatgi — Massachusetts;Qinghua Liu;Praneeth Netrapalli;Csaba Szepesvári;Debarati Das;Jacob Gilbert;Mohammadtaghi Hajiaghayi;Tomasz Kociumaka;B. Saha;K. Bringmann;Nick Fischer — Weizmann;Ce Jin;Yinzhan Xu — Massachusetts;Virginia Vassilevska Williams;Yinzhan Xu;Josh Alman;Kevin Rao;Hamed Hatami;—. XiangMeng;McGill University;Edith Cohen;Xin Lyu;Tamás Jelani Nelson;Uri Stemmer — Google;Research;Daniel Alabi;Pravesh K. Kothari;Pranay Tankala;Prayaag Venkat;Fred Zhang;Samuel B. Hopkins;Gautam Kamath;Shyam Narayanan — Massachusetts;Marco Gaboardi;R. Impagliazzo;Rex Lei;Satchit Sivakumar;Jessica Sorrell;T. Korhonen;Marco Bressan;Matthias Lanzinger;Huck Bennett;Mahdi Cheraghchi;V. Guruswami;João Ribeiro;Jan Dreier;Nikolas Mählmann;Sebastian Siebertz — TU Wien;The Randomized k ;Conjecture Is;False;Sébastien Bubeck;Christian Coester;Yuval Rabani — Microsoft;Wei;Ethan Mook;Daniel Wichs;Joshua Brakensiek;Sai Sandeep — Stanford;University;Lorenzo Ciardo;Stanislav Živný;Amey Bhangale;Subhash Khot;Dor Minzer;David Ellis;Guy Kindler;Noam Lifshitz;Ronen Eldan;Dan Mikulincer;George Christodoulou;E. Koutsoupias;Annamária Kovács;José Correa;Andrés Cristi;Xi Chen;Matheus Venturyne;Xavier Ferreira;David C. Parkes;Yang Cai;Jinzhao Wu;Zhengyang Liu;Zeyu Ren;Zihe Wang;Ravishankar Krishnaswamy;Shi Li;Varun Suriyanarayana - 通讯作者:
Varun Suriyanarayana
Approximation algorithms for data placement on parallel disks
并行磁盘上数据放置的近似算法
- DOI:
10.1145/1597036.1597037 - 发表时间:
2009 - 期刊:
- 影响因子:0
- 作者:
L. Golubchik;Sanjeev Khanna;Samir Khuller;R. Thurimella;An Zhu - 通讯作者:
An Zhu
A greedy approximation algorithm for minimum-gap scheduling
- DOI:
10.1007/s10951-016-0492-y - 发表时间:
2016-07-27 - 期刊:
- 影响因子:1.800
- 作者:
Marek Chrobak;Uriel Feige;Mohammad Taghi Hajiaghayi;Sanjeev Khanna;Fei Li;Seffi Naor - 通讯作者:
Seffi Naor
Sanjeev Khanna的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Sanjeev Khanna', 18)}}的其他基金
AF: Small: Sublinear Algorithms for Flows, Matchings, and Routing Problems
AF:小:流、匹配和路由问题的次线性算法
- 批准号:
2008305 - 财政年份:2020
- 资助金额:
$ 59.94万 - 项目类别:
Standard Grant
AF: Small: Sublinear Algorithms for Graph Optimization Problems
AF:小:图优化问题的次线性算法
- 批准号:
1617851 - 财政年份:2016
- 资助金额:
$ 59.94万 - 项目类别:
Standard Grant
AF: EAGER: Small Space Algorithms and Representations for Graph Optimization Problems
AF:EAGER:图优化问题的小空间算法和表示
- 批准号:
1552909 - 财政年份:2015
- 资助金额:
$ 59.94万 - 项目类别:
Standard Grant
AF: Small: Cut, Flow, and Matching Problems in Graphs
AF:小:图中的切割、流动和匹配问题
- 批准号:
1116961 - 财政年份:2011
- 资助金额:
$ 59.94万 - 项目类别:
Standard Grant
III: Medium: Collaborative Research: Optimization with Sparse Priors--Algorithms, Indices, and Economic Incentives
III:媒介:协作研究:稀疏先验优化——算法、指数和经济激励
- 批准号:
0904314 - 财政年份:2009
- 资助金额:
$ 59.94万 - 项目类别:
Continuing Grant
Effectiveness of problem based learning in a materials science course in the engineering curriculum
基于问题的学习在工程课程材料科学课程中的有效性
- 批准号:
0836914 - 财政年份:2009
- 资助金额:
$ 59.94万 - 项目类别:
Standard Grant
Collaborative Research: CT-T: DoS Prevention in Shared Channels
合作研究:CT-T:共享通道中的 DoS 预防
- 批准号:
0524269 - 财政年份:2005
- 资助金额:
$ 59.94万 - 项目类别:
Standard Grant
Acquisition of a Nanomechanical Testing Platform to Establish a User Center for Nanomecanical Characterization Materials
收购纳米力学测试平台,建立纳米力学表征材料用户中心
- 批准号:
0420859 - 财政年份:2004
- 资助金额:
$ 59.94万 - 项目类别:
Standard Grant
Development and Manufacturing of Highly Damage Resistant Fiber Glass Reinforced Window Panels for Buildings in Hurricane Prone Areas
为飓风多发地区的建筑物开发和制造高抗损伤玻璃纤维增强窗板
- 批准号:
0196428 - 财政年份:2001
- 资助金额:
$ 59.94万 - 项目类别:
Continuing Grant
相似国自然基金
Research on Quantum Field Theory without a Lagrangian Description
- 批准号:24ZR1403900
- 批准年份:2024
- 资助金额:0.0 万元
- 项目类别:省市级项目
Cell Research
- 批准号:31224802
- 批准年份:2012
- 资助金额:24.0 万元
- 项目类别:专项基金项目
Cell Research
- 批准号:31024804
- 批准年份:2010
- 资助金额:24.0 万元
- 项目类别:专项基金项目
Cell Research (细胞研究)
- 批准号:30824808
- 批准年份:2008
- 资助金额:24.0 万元
- 项目类别:专项基金项目
Research on the Rapid Growth Mechanism of KDP Crystal
- 批准号:10774081
- 批准年份:2007
- 资助金额:45.0 万元
- 项目类别:面上项目
相似海外基金
Collaborative Research: AF: Medium: The Communication Cost of Distributed Computation
合作研究:AF:媒介:分布式计算的通信成本
- 批准号:
2402836 - 财政年份:2024
- 资助金额:
$ 59.94万 - 项目类别:
Continuing Grant
Collaborative Research: AF: Medium: Foundations of Oblivious Reconfigurable Networks
合作研究:AF:媒介:遗忘可重构网络的基础
- 批准号:
2402851 - 财政年份:2024
- 资助金额:
$ 59.94万 - 项目类别:
Continuing Grant
Collaborative Research: AF: Small: New Directions in Algorithmic Replicability
合作研究:AF:小:算法可复制性的新方向
- 批准号:
2342244 - 财政年份:2024
- 资助金额:
$ 59.94万 - 项目类别:
Standard Grant
Collaborative Research: AF: Small: Exploring the Frontiers of Adversarial Robustness
合作研究:AF:小型:探索对抗鲁棒性的前沿
- 批准号:
2335411 - 财政年份:2024
- 资助金额:
$ 59.94万 - 项目类别:
Standard Grant
NSF-BSF: Collaborative Research: AF: Small: Algorithmic Performance through History Independence
NSF-BSF:协作研究:AF:小型:通过历史独立性实现算法性能
- 批准号:
2420942 - 财政年份:2024
- 资助金额:
$ 59.94万 - 项目类别:
Standard Grant
Collaborative Research: AF: Medium: Algorithms Meet Machine Learning: Mitigating Uncertainty in Optimization
协作研究:AF:媒介:算法遇见机器学习:减轻优化中的不确定性
- 批准号:
2422926 - 财政年份:2024
- 资助金额:
$ 59.94万 - 项目类别:
Continuing Grant
Collaborative Research: AF: Small: Structural Graph Algorithms via General Frameworks
合作研究:AF:小型:通过通用框架的结构图算法
- 批准号:
2347322 - 财政年份:2024
- 资助金额:
$ 59.94万 - 项目类别:
Standard Grant
Collaborative Research: AF: Small: Real Solutions of Polynomial Systems
合作研究:AF:小:多项式系统的实数解
- 批准号:
2331401 - 财政年份:2024
- 资助金额:
$ 59.94万 - 项目类别:
Standard Grant
Collaborative Research: AF: Small: Real Solutions of Polynomial Systems
合作研究:AF:小:多项式系统的实数解
- 批准号:
2331400 - 财政年份:2024
- 资助金额:
$ 59.94万 - 项目类别:
Standard Grant
Collaborative Research: AF: Medium: Fast Combinatorial Algorithms for (Dynamic) Matchings and Shortest Paths
合作研究:AF:中:(动态)匹配和最短路径的快速组合算法
- 批准号:
2402283 - 财政年份:2024
- 资助金额:
$ 59.94万 - 项目类别:
Continuing Grant