AF: Small: Sublinear Algorithms for Graph Optimization Problems

AF:小:图优化问题的次线性算法

基本信息

  • 批准号:
    1617851
  • 负责人:
  • 金额:
    $ 45万
  • 依托单位:
  • 依托单位国家:
    美国
  • 项目类别:
    Standard Grant
  • 财政年份:
    2016
  • 资助国家:
    美国
  • 起止时间:
    2016-09-01 至 2021-08-31
  • 项目状态:
    已结题

项目摘要

Very-large scale graphs routinely arise in applications where the data describes pairwise relationships among a set of objects. Some standard examples include the Web graph, social networks, and biological networks. The prevalence of such large data sets has led to a rapidly growing interest in the design of sublinear algorithms, that is, algorithms whose computational resource requirements are substantially smaller than the input size. As vast amounts of networked data is being collected and processed in diverse application domains, sublinear algorithms that accurately compute and describe relevant properties of the data will increasingly play an important role in computing on such data. The goal of this project is to develop sublinear algorithms for several fundamental graph optimization problems. The specific graph problems studied in this project are of both theoretical and practical interest, and are among the most well-studied problems in combinatorial optimization. Additionally, a study of these problems through the lens of sublinear algorithms is likely to yield new insights into computational aspects of these fundamental problems. The research proposed here will go hand-in-hand with educational and student-training initiatives, including mentoring and training of undergraduate and graduate students, and teaching in programs that introduce high-school students to exciting ideas in theoretical computer science.The research focus of this project is broadly divided into three parts. In the first part, the PIs consider streaming algorithms for graph problems where an input graph is revealed as a sequence of edge insertions and deletions. Some representative problems studied in this part include matching and cut problems in graphs. While both cuts and matchings have received considerable attention in the streaming literature, several important questions concerning their computability in the streaming model remain unresolved. In the second part, they consider communication-efficient protocols in a distributed setting when the input graph is partitioned across multiple sites. This model offers a natural abstraction for distributed computation and is closely related to the streaming model. A representative problem here is to understand the communication complexity of the maximum matching problem. The third part of this project investigates a new model for sketching graphs that consist of a (large) static part and a (small) dynamic part. The goal here is to understand if there exist compact sketches for several fundamental graph problems whose size is proportional to the size of the dynamic part of the input graph such that any updates to the dynamic part can be applied directly to the sketch.
超大规模图通常出现在数据描述一组对象之间的成对关系的应用中。一些标准的例子包括Web图、社交网络和生物网络。这种大数据集的流行导致了对次线性算法设计的兴趣迅速增长,次线性算法是指计算资源需求远小于输入大小的算法。随着大量的网络数据在不同的应用领域中被收集和处理,准确计算和描述数据的相关属性的次线性算法将在此类数据的计算中发挥越来越重要的作用。这个项目的目标是为几个基本的图优化问题开发次线性算法。在这个项目中研究的特定的图形问题的理论和实际利益,是在组合优化中最好的研究问题之一。此外,这些问题的研究,通过透镜的次线性算法可能会产生新的见解,这些基本问题的计算方面。本研究计划将与教育和学生培训计划齐头并进,包括指导和培训本科生和研究生,以及在课程中向高中生介绍理论计算机科学中令人兴奋的想法。本项目的研究重点大致分为三个部分。在第一部分中,PI考虑流算法的图形问题,其中输入图显示为一系列的边缘插入和删除。这一部分研究了图的匹配和割问题。虽然切割和匹配在流媒体文献中受到了相当大的关注,但关于它们在流媒体模型中的可计算性的几个重要问题仍然没有得到解决。在第二部分中,当输入图被划分到多个站点时,他们考虑了分布式环境中的通信高效协议。该模型为分布式计算提供了一个自然的抽象,并且与流模型密切相关。这里的一个代表性问题是理解最大匹配问题的通信复杂性。本项目的第三部分研究了一种新的模型,用于绘制由(大)静态部分和(小)动态部分组成的图形。这里的目标是了解是否存在几个基本图问题的紧凑草图,这些问题的大小与输入图的动态部分的大小成比例,以便对动态部分的任何更新都可以直接应用于草图。

项目成果

期刊论文数量(2)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
Near-linear Size Hypergraph Cut Sparsifiers
Sublinear Time Hypergraph Sparsification via Cut and Edge Sampling Queries
  • DOI:
    10.4230/lipics.icalp.2021.53
  • 发表时间:
    2021-06
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Yu Chen;S. Khanna;Ansh Nagda
  • 通讯作者:
    Yu Chen;S. Khanna;Ansh Nagda
{{ 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) 时间内实现最大二分匹配
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)}}的其他基金

Collaborative Research: AF: Medium: Fast Combinatorial Algorithms for (Dynamic) Matchings and Shortest Paths
合作研究:AF:中:(动态)匹配和最短路径的快速组合算法
  • 批准号:
    2402284
  • 财政年份:
    2024
  • 资助金额:
    $ 45万
  • 项目类别:
    Continuing Grant
AF: Small: Sublinear Algorithms for Flows, Matchings, and Routing Problems
AF:小:流、匹配和路由问题的次线性算法
  • 批准号:
    2008305
  • 财政年份:
    2020
  • 资助金额:
    $ 45万
  • 项目类别:
    Standard Grant
AF: EAGER: Small Space Algorithms and Representations for Graph Optimization Problems
AF:EAGER:图优化问题的小空间算法和表示
  • 批准号:
    1552909
  • 财政年份:
    2015
  • 资助金额:
    $ 45万
  • 项目类别:
    Standard Grant
AF: Small: Cut, Flow, and Matching Problems in Graphs
AF:小:图中的切割、流动和匹配问题
  • 批准号:
    1116961
  • 财政年份:
    2011
  • 资助金额:
    $ 45万
  • 项目类别:
    Standard Grant
III: Medium: Collaborative Research: Optimization with Sparse Priors--Algorithms, Indices, and Economic Incentives
III:媒介:协作研究:稀疏先验优化——算法、指数和经济激励
  • 批准号:
    0904314
  • 财政年份:
    2009
  • 资助金额:
    $ 45万
  • 项目类别:
    Continuing Grant
Effectiveness of problem based learning in a materials science course in the engineering curriculum
基于问题的学习在工程课程材料科学课程中的有效性
  • 批准号:
    0836914
  • 财政年份:
    2009
  • 资助金额:
    $ 45万
  • 项目类别:
    Standard Grant
Cuts, Flows, and Network Routing
剪切、流和网络路由
  • 批准号:
    0635084
  • 财政年份:
    2006
  • 资助金额:
    $ 45万
  • 项目类别:
    Standard Grant
Collaborative Research: CT-T: DoS Prevention in Shared Channels
合作研究:CT-T:共享通道中的 DoS 预防
  • 批准号:
    0524269
  • 财政年份:
    2005
  • 资助金额:
    $ 45万
  • 项目类别:
    Standard Grant
Acquisition of a Nanomechanical Testing Platform to Establish a User Center for Nanomecanical Characterization Materials
收购纳米力学测试平台,建立纳米力学表征材料用户中心
  • 批准号:
    0420859
  • 财政年份:
    2004
  • 资助金额:
    $ 45万
  • 项目类别:
    Standard Grant
Development and Manufacturing of Highly Damage Resistant Fiber Glass Reinforced Window Panels for Buildings in Hurricane Prone Areas
为飓风多发地区的建筑物开发和制造高抗损伤玻璃纤维增​​强窗板
  • 批准号:
    0196428
  • 财政年份:
    2001
  • 资助金额:
    $ 45万
  • 项目类别:
    Continuing Grant

相似国自然基金

昼夜节律性small RNA在血斑形成时间推断中的法医学应用研究
  • 批准号:
  • 批准年份:
    2024
  • 资助金额:
    0.0 万元
  • 项目类别:
    省市级项目
tRNA-derived small RNA上调YBX1/CCL5通路参与硼替佐米诱导慢性疼痛的机制研究
  • 批准号:
    n/a
  • 批准年份:
    2022
  • 资助金额:
    10.0 万元
  • 项目类别:
    省市级项目
Small RNA调控I-F型CRISPR-Cas适应性免疫性的应答及分子机制
  • 批准号:
    32000033
  • 批准年份:
    2020
  • 资助金额:
    24.0 万元
  • 项目类别:
    青年科学基金项目
Small RNAs调控解淀粉芽胞杆菌FZB42生防功能的机制研究
  • 批准号:
    31972324
  • 批准年份:
    2019
  • 资助金额:
    58.0 万元
  • 项目类别:
    面上项目
变异链球菌small RNAs连接LuxS密度感应与生物膜形成的机制研究
  • 批准号:
    81900988
  • 批准年份:
    2019
  • 资助金额:
    21.0 万元
  • 项目类别:
    青年科学基金项目
基于small RNA 测序技术解析鸽分泌鸽乳的分子机制
  • 批准号:
    31802058
  • 批准年份:
    2018
  • 资助金额:
    26.0 万元
  • 项目类别:
    青年科学基金项目
肠道细菌关键small RNAs在克罗恩病发生发展中的功能和作用机制
  • 批准号:
    31870821
  • 批准年份:
    2018
  • 资助金额:
    56.0 万元
  • 项目类别:
    面上项目
Small RNA介导的DNA甲基化调控的水稻草矮病毒致病机制
  • 批准号:
    31772128
  • 批准年份:
    2017
  • 资助金额:
    60.0 万元
  • 项目类别:
    面上项目
基于small RNA-seq的针灸治疗桥本甲状腺炎的免疫调控机制研究
  • 批准号:
    81704176
  • 批准年份:
    2017
  • 资助金额:
    20.0 万元
  • 项目类别:
    青年科学基金项目
水稻OsSGS3与OsHEN1调控small RNAs合成及其对抗病性的调节
  • 批准号:
    91640114
  • 批准年份:
    2016
  • 资助金额:
    85.0 万元
  • 项目类别:
    重大研究计划

相似海外基金

CSR: Small: Leveraging Physical Side-Channels for Good
CSR:小:利用物理侧通道做好事
  • 批准号:
    2312089
  • 财政年份:
    2024
  • 资助金额:
    $ 45万
  • 项目类别:
    Standard Grant
NeTS: Small: NSF-DST: Modernizing Underground Mining Operations with Millimeter-Wave Imaging and Networking
NeTS:小型:NSF-DST:利用毫米波成像和网络实现地下采矿作业现代化
  • 批准号:
    2342833
  • 财政年份:
    2024
  • 资助金额:
    $ 45万
  • 项目类别:
    Standard Grant
CPS: Small: NSF-DST: Autonomous Operations of Multi-UAV Uncrewed Aerial Systems using Onboard Sensing to Monitor and Track Natural Disaster Events
CPS:小型:NSF-DST:使用机载传感监测和跟踪自然灾害事件的多无人机无人航空系统自主操作
  • 批准号:
    2343062
  • 财政年份:
    2024
  • 资助金额:
    $ 45万
  • 项目类别:
    Standard Grant
Collaborative Research: FET: Small: Reservoir Computing with Ion-Channel-Based Memristors
合作研究:FET:小型:基于离子通道忆阻器的储层计算
  • 批准号:
    2403559
  • 财政年份:
    2024
  • 资助金额:
    $ 45万
  • 项目类别:
    Standard Grant
オミックス解析を用いたブドウ球菌 small colony variants の包括的特徴づけ
使用组学分析全面表征葡萄球菌小菌落变体
  • 批准号:
    24K13443
  • 财政年份:
    2024
  • 资助金额:
    $ 45万
  • 项目类别:
    Grant-in-Aid for Scientific Research (C)
AF: Small: Problems in Algorithmic Game Theory for Online Markets
AF:小:在线市场的算法博弈论问题
  • 批准号:
    2332922
  • 财政年份:
    2024
  • 资助金额:
    $ 45万
  • 项目类别:
    Standard Grant
Collaborative Research: FET: Small: Algorithmic Self-Assembly with Crisscross Slats
合作研究:FET:小型:十字交叉板条的算法自组装
  • 批准号:
    2329908
  • 财政年份:
    2024
  • 资助金额:
    $ 45万
  • 项目类别:
    Standard Grant
NeTS: Small: ML-Driven Online Traffic Analysis at Multi-Terabit Line Rates
NeTS:小型:ML 驱动的多太比特线路速率在线流量分析
  • 批准号:
    2331111
  • 财政年份:
    2024
  • 资助金额:
    $ 45万
  • 项目类别:
    Standard Grant
Collaborative Research: SHF: Small: LEGAS: Learning Evolving Graphs At Scale
协作研究:SHF:小型:LEGAS:大规模学习演化图
  • 批准号:
    2331302
  • 财政年份:
    2024
  • 资助金额:
    $ 45万
  • 项目类别:
    Standard Grant
Collaborative Research: SHF: Small: LEGAS: Learning Evolving Graphs At Scale
协作研究:SHF:小型:LEGAS:大规模学习演化图
  • 批准号:
    2331301
  • 财政年份:
    2024
  • 资助金额:
    $ 45万
  • 项目类别:
    Standard Grant
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了