BSF: 2014414: New Challenges and Perspectives in Online Algorithms
BSF:2014414:在线算法的新挑战和前景
基本信息
- 批准号:1540541
- 负责人:
- 金额:$ 4万
- 依托单位:
- 依托单位国家:美国
- 项目类别:Standard Grant
- 财政年份:2015
- 资助国家:美国
- 起止时间:2015-09-01 至 2019-08-31
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
While the traditional design and analysis of algorithms assumes that complete knowledge of the entire input is available to the algorithm, the area of online algorithms deals with the case where the input is revealed in parts, and the online algorithm is required to respond to each new part immediately upon arrival, without knowledge of the future. Previous decisions of the online algorithm cannot be revoked. Thus, the main issue in online computation is obtaining good performance in the face of uncertainty, since the future is unknown to the algorithm. The problems in this setting arise in all of computer science, as well in much of sequential decision-making, machine learning, and many other areas.The proposed research is focused on a deeper investigation of the primal-dual approach to online algorithm design. The topics investigated in this project are (a) extending the success of linear optimization to the convex case, (b) relaxing monotonicity of the variables and developing principled approaches for algorithms with preemption, and (c) understanding the connection of online primal-dual approaches and online machine learning algorithms. As part of the broader impact, the research is likely to lead to better algorithms for a variety of problems both in traditional algorithm design and in other areas like machine learning and algorithmic game theory.
虽然传统的算法设计和分析假设整个输入的完整知识可用于算法,但在线算法领域处理输入以部分形式显示的情况,并且在线算法需要在到达时立即响应每个新部分,而不知道未来。在线算法的先前决定不能被撤销。因此,在线计算中的主要问题是在面对不确定性时获得良好的性能,因为未来对算法来说是未知的。在这种情况下出现的问题在所有的计算机科学,以及在许多顺序决策,机器学习,和许多其他areages.The建议的研究集中在一个更深入的调查的原始-对偶方法在线算法设计。在这个项目中研究的主题是(a)扩展线性优化的成功凸的情况下,(B)放松单调的变量和开发原则的方法与抢占算法,和(c)了解在线原始对偶方法和在线机器学习算法的连接。作为更广泛影响的一部分,这项研究可能会为传统算法设计以及机器学习和算法博弈论等其他领域的各种问题带来更好的算法。
项目成果
期刊论文数量(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 }}
Anupam Gupta其他文献
Probing hard color-singlet exchange in pp̄ collisions at √s = 630 GeV and 1800 GeV
探测 √s = 630 GeV 和 1800 GeV pp̄ 碰撞中的硬颜色-单线态交换
- DOI:
- 发表时间:
1998 - 期刊:
- 影响因子:0
- 作者:
B. Abbott;M. Abolins;V. Abramov;B. Acharya;I. Adam;D. Adams;M. Adams;S. Ahn;H. Aihara;G. Alves;N. Amos;E. Anderson;R. Astur;M. Baarmand;V. Babintsev;L. Babukhadia;A. Baden;B. Baldin;S. Banerjee;J. Bantly;E. Barberis;P. Baringer;J. Bartlett;A. Belyaev;S. Beri;I. Bertram;V. Bezzubov;P. Bhat;V. Bhatnagar;M. Bhattacharjee;N. Biswas;G. Blazey;S. Blessing;P. Bloom;A. Boehnlein;N. Bojko;F. Borcherding;C. Boswell;A. Brandt;R. Breedon;R. Brock;A. Bross;D. Buchholz;V. S. Burtovoǐ;J. Butler;W. Carvalho;D. Casey;Z. Casilum;H. Castilla;D. Chakraborty;S. Chang;S. Chekulaev;Wei Chen;Suyong Choi;S. Chopra;B. Choudhary;J. Christenson;M. Chung;D. Claes;A. Clark;W. G. Cobau;J. Cochran;L. Coney;W. Cooper;C. Cretsinger;D. Cullen;M. Cummings;D. Cutts;O. Dahl;K. Davis;K. De;K. D. Signore;M. Demarteau;D. Denisov;S. Denisov;H. Diehl;M. Diesburg;G. D. Loreto;P. Draper;Y. Ducros;L. Dudko;S. Dugad;A. Dyshkant;D. Edmunds;J. Ellison;V. Elvira;R. Engelmann;S. Eno;G. Eppley;P. Ermolov;O. Eroshin;V. Evdokimov;T. Fahland;M. Fatyga;S. Feher;D. Fein;T. Ferbel;G. Finocchiaro;H. Fisk;Y. Fisyak;E. Flattum;G. Forden;M. Fortner;K. Frame;S. Fuess;E. Gallas;A. Galyaev;P. Gartung;V. Gavrilov;T. Geld;R. Genik;K. Genser;C. Gerber;Y. Gershtein;B. Gibbard;B. Gobbi;B. Gomez;G. Gomez;P. Goncharov;J. Solı́s;H. Gordon;L. Goss;K. Gounder;A. Goussiou;N. Graf;P. Grannis;D. Green;H. Greenlee;S. Grinstein;P. Grudberg;S. Grünendahl;G. Guglielmo;J. Guida;J. Guida;Anupam Gupta;S. N. Gurzhiev;G. Gutiérrez;P. Gutierrez;N. Hadley;H. Haggerty;S. Hagopian;V. Hagopian;K. Hahn;R. E. Hall;P. Hanlet;S. Hansen;J. Hauptman;D. Hedin;A. Heinson;U. Heintz;R. Hernández;T. Heuring;R. Hirosky;J. Hobbs;B. Hoeneisen;J. S. Hoftun;F. Hsieh;H. Ting;H. Tong;A. Ito;E. James;J. Jaques;S. Jerger;R. Jesik;T. Joffe;K. Johns;M. Johnson;A. Jonckheere;M. Jones;H. Jöstlein;S. Jun;C. Jung;S. Kahn;G. Kalbfleisch;D. Karmanov;D. Karmgard;R. Kehoe;M. Kelly;S. Kim;B. Klima;C. Klopfenstein;W. Ko;J. Kohli;D. Koltick;A. V. Kostritskiy;J. Kotcher;A. Kotwal;A. Kozelov;E. Kozlovsky;J. Krane;M. Krishnaswamy;S. Krzywdzinski;S. Kuleshov;Y. Kulik;S. Kunori;F. Landry;G. Landsberg;B. Lauer;A. Leflat;Jiang Li;Q. Li;J. Lima;D. Lincoln;S. Linn;J. Linnemann;R. Lipton;F. Lobkowicz;S. Loken;A. Lucotte;L. Lueking;A. Lyon;A. Maciel;R. Madaras;R. Madden;L. Magaña;V. Manankov;S. Mani;H. Mao;R. Markeloff;T. Marshall;M. Martin;K. Mauritz;B. May;A. Mayorov;R. Mccarthy;J. Mcdonald;T. Mckibben;J. McKinley;T. Mcmahon;H. Melanson;M. Merkin;K. Merritt;C. Miao;H. Miettinen;A. Mincer;C. Mishra;N. Mokhov;N. Mondal;H. Montgomery;P. Mooney;M. Mostafá;H. Motta;C. Murphy;F. Nang;M. Narain;V. S. Narasimham;A. Narayanan;H. Neal;J. Negret;P. Némethy;D. Norman;L. Oesch;V. Oguri;E. Oliveira;E. Oltman;N. Oshima;D. Owen;P. Padley;A. Para;Y. M. Park;R. Partridge;N. Parua;M. Paterno;B. Pawlik;J. Perkins;Marco Peters;R. Piegaia;H. Piekarz;Y. Pischalnikov;B. Pope;H. Prosper;S. Protopopescu;J. Qian;P. Z. Quintas;R. Raja;S. Rajagopalan;O. Ramirez;S. Reucroft;M. Rijssenbeek;T. Rockwell;M. Roco;P. Rubinov;R. Ruchti;J. Rutherfoord;A. Sanchez;A. Santoro;L. Sawyer;R. Schamberger;H. Schellman;J. Sculli;E. Shabalina;C. Shaffer;H. Shankar;R. K. Shivpuri;D. Shpakov;M. Shupe;H. Singh;J. Singh;V. Sirotenko;E. Smith;R. Smith;R. Snihur;G. Snow;J. Snow;S. Snyder;J. Solomon;M. Sosebee;N. Sotnikova;M. Souza;G. Steinbrück;R. Stephens;M. L. Stevenson;D. Stewart;F. Stichelbaut;D. Stoker;V. Stolin;D. Stoyanova;M. Strauss;K. Streets;M. Strovink;A. Sznajder;P. Tamburello;J. Tarazi;M. Tartaglia;T. Thomas;J. Thompson;T. Trippe;P. Tuts;V. Vaniev;N. Varelas;E. Varnes;D. Vititoe;A. Volkov;A. Vorobiev;H. Wahl;G. Wang;J. Warchoł;G. Watts;M. Wayne;H. Weerts;A. White;J. White;J. Wightman;S. Willis;S. Wimpenny;J. Wirjawan;J. Womersley;E. Won;D. Wood;Z. Wu;R. Yamada;P. Yamin;T. Yasuda;P. Yepes;K. Yip;C. Yoshikawa;S. Youssef;J. Yu;Y. Yu;B. Zhang;Y. Zhou;Z. Zhou;Z. H. Zhu;M. Zielinski;D. Zieminska;A. Zieminski;E. Zverev;A. Zylberstejn - 通讯作者:
A. Zylberstejn
The Connectivity Threshold for Dense Graphs
密集图的连接阈值
- DOI:
- 发表时间:
2021 - 期刊:
- 影响因子:0
- 作者:
Anupam Gupta;Euiwoong Lee;Jason Li - 通讯作者:
Jason Li
Efficient cost-sharing mechanisms for prize-collecting problems
针对奖品收集问题的有效成本分摊机制
- DOI:
10.1007/s10107-014-0781-1 - 发表时间:
2015 - 期刊:
- 影响因子:2.7
- 作者:
Anupam Gupta;J. Könemann;S. Leonardi;R. Ravi;G. Schäfer - 通讯作者:
G. Schäfer
Chasing convex bodies with linear competitive ratio (invited paper)
线性竞争比追逐凸体(特邀论文)
- DOI:
10.1145/3406325.3465354 - 发表时间:
2021 - 期刊:
- 影响因子:0
- 作者:
C. Argue;Anupam Gupta;Guru Guruganesh;Ziye Tang - 通讯作者:
Ziye Tang
Anupam Gupta的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Anupam Gupta', 18)}}的其他基金
Collaborative Research: AF: Medium: Algorithms Meet Machine Learning: Mitigating Uncertainty in Optimization
协作研究:AF:媒介:算法遇见机器学习:减轻优化中的不确定性
- 批准号:
2422926 - 财政年份:2024
- 资助金额:
$ 4万 - 项目类别:
Continuing Grant
NSF: STOC 2024 Conference Student Travel Support
NSF:STOC 2024 会议学生旅行支持
- 批准号:
2421504 - 财政年份:2024
- 资助金额:
$ 4万 - 项目类别:
Standard Grant
AF: Small: Towards New Relaxations for Online Algorithms
AF:小:在线算法的新放松
- 批准号:
2224718 - 财政年份:2022
- 资助金额:
$ 4万 - 项目类别:
Standard Grant
Collaborative Research: AF: Medium: Algorithms Meet Machine Learning: Mitigating Uncertainty in Optimization
协作研究:AF:媒介:算法遇见机器学习:减轻优化中的不确定性
- 批准号:
1955785 - 财政年份:2020
- 资助金额:
$ 4万 - 项目类别:
Continuing Grant
Collaborative Research: AF: Small: Combinatorial Optimization for Stochastic Inputs
合作研究:AF:小:随机输入的组合优化
- 批准号:
2006953 - 财政年份:2020
- 资助金额:
$ 4万 - 项目类别:
Standard Grant
AF: Small: New Approaches for Approximation and Online Algorithms
AF:小:近似和在线算法的新方法
- 批准号:
1907820 - 财政年份:2019
- 资助金额:
$ 4万 - 项目类别:
Standard Grant
CCF-BSF: AF: Small: Metric Embeddings and Partitioning for Minor-Closed Graph Families
CCF-BSF:AF:小:次封闭图族的度量嵌入和分区
- 批准号:
1617790 - 财政年份:2016
- 资助金额:
$ 4万 - 项目类别:
Standard Grant
AF: Small: Approximation Algorithms for Uncertain Environments and Graph Partitioning
AF:小:不确定环境和图分区的近似算法
- 批准号:
1319811 - 财政年份:2013
- 资助金额:
$ 4万 - 项目类别:
Standard Grant
AF: Small: Future Directions in Approximation Algorithms Research
AF:小:近似算法研究的未来方向
- 批准号:
1016799 - 财政年份:2010
- 资助金额:
$ 4万 - 项目类别:
Standard Grant
Collaborative Research: Emerging Directions in Network Design and Optimization
协作研究:网络设计和优化的新兴方向
- 批准号:
0729022 - 财政年份:2007
- 资助金额:
$ 4万 - 项目类别:
Standard Grant