Practical Competitive Analysis (Computer Science)
实用竞争分析(计算机科学)
基本信息
- 批准号:9450075
- 负责人:
- 金额:$ 23.88万
- 依托单位:
- 依托单位国家:美国
- 项目类别:Standard Grant
- 财政年份:1994
- 资助国家:美国
- 起止时间:1994-09-01 至 1996-08-31
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
An algorithm is said to be online if it receives input in a sequence of requests, and must service each request as it arrives without any knowledge of the future. Many fundamental problems in computer science are inherently online. A commonly used method of analyzing online algorithms is competitive analysis, where the performance of the online algorithm is compared to the performance of the optimal clairvoyant algorithm. There are several practical problems with the usual style of competitive analysis, including the use of worst care adversary, the lack of attention to implementation efficiency, and the lack of empirical evidence concerning the performance of competitive algorithms. The goal of this project is to help bridge the gap between theory and practice in this rapidly growing area by developing efficient, adaptive algorithms for fundamental systems problems. These algorithms should perform well against a statistical adversary, and will be empirically evaluated. Interactive activities include: participation in the mentoring and outreach programs of Women in Engineering; development of and experimentation with software for teaching math to girls, via collaboration with Professor Steve Tanimoto's research group at the University of Washington (UW) and with Professor Maria Klawe's E- GEMS project at the University of British Columbia; and teaching an undergraduate course and seminars in computer science and undertaking joint research with other members of the computer science faculty at UW.
如果一个算法在一系列请求中接收到输入,并且必须在不知道未来的情况下为每个请求提供服务,则该算法被称为在线。 计算机科学中的许多基本问题本质上都是在线的。 分析在线算法的常用方法是竞争分析,其中将在线算法的性能与最佳透视算法的性能进行比较。 通常的竞争分析风格有几个实际问题,包括 使用最坏的照顾对手,缺乏对执行效率的关注,以及缺乏关于竞争算法性能的经验证据。 这个项目的目标是帮助弥合理论和实践之间的差距,在这个快速增长的领域,通过开发有效的,自适应算法的基本系统问题。 这些算法应该对统计对手表现良好,并将进行经验评估。 互动活动包括:参与妇女参与工程的指导和推广方案;通过与华盛顿大学Steve Tanimoto教授的研究小组和不列颠哥伦比亚省Maria Klawe教授的E-GEMS项目合作,开发和试验女孩数学教学软件;教授计算机科学的本科课程和研讨会,并与华盛顿大学计算机科学系的其他成员进行联合研究。
项目成果
期刊论文数量(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 }}
Anna Karlin其他文献
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
Anna Karlin的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Anna Karlin', 18)}}的其他基金
AF: SMALL : Algorithmic and Game Theoretic Problems Arising in Modern Matching Markets
AF:小:现代匹配市场中出现的算法和博弈论问题
- 批准号:
1813135 - 财政年份:2018
- 资助金额:
$ 23.88万 - 项目类别:
Standard Grant
AF: Small: Towards More Realistic Models in Algorithmic Mechanism Design
AF:小:算法机制设计中迈向更现实的模型
- 批准号:
1420381 - 财政年份:2014
- 资助金额:
$ 23.88万 - 项目类别:
Standard Grant
AF: Small: Beyond Worst-Case Analysis in Approximation Algorithms, Algorithmic Mechanism Design and Online Algorithms
AF:小:超越近似算法、算法机制设计和在线算法中的最坏情况分析
- 批准号:
1016509 - 财政年份:2010
- 资助金额:
$ 23.88万 - 项目类别:
Standard Grant
Mechanism Design for Profit Maximization
利润最大化的机制设计
- 批准号:
0635147 - 财政年份:2006
- 资助金额:
$ 23.88万 - 项目类别:
Standard Grant
相似海外基金
Collaborative Research: Mathematical and Experimental Analysis of Competitive and Predator-Prey Models: Conditional Dispersal on Patches to Landscapes
合作研究:竞争模型和捕食者-被捕食模型的数学和实验分析:景观斑块的条件扩散
- 批准号:
2150947 - 财政年份:2022
- 资助金额:
$ 23.88万 - 项目类别:
Standard Grant
Analysis and Characterization of Advanced Composites for Competitive Failure Models
用于竞争失效模型的先进复合材料的分析和表征
- 批准号:
RGPIN-2022-03315 - 财政年份:2022
- 资助金额:
$ 23.88万 - 项目类别:
Discovery Grants Program - Individual
Collaborative Research: Mathematical and Experimental Analysis of Competitive and Predator-Prey Models: Conditional Dispersal on Patches to Landscapes
合作研究:竞争模型和捕食者-被捕食模型的数学和实验分析:景观斑块的条件扩散
- 批准号:
2150945 - 财政年份:2022
- 资助金额:
$ 23.88万 - 项目类别:
Standard Grant
Collaborative Research: Mathematical and Experimental Analysis of Competitive and Predator-Prey Models: Conditional Dispersal on Patches to Landscapes
合作研究:竞争模型和捕食者-被捕食模型的数学和实验分析:景观斑块的条件扩散
- 批准号:
2150946 - 财政年份:2022
- 资助金额:
$ 23.88万 - 项目类别:
Standard Grant
AF: Small: Metric Information Theory, Online Learning, and Competitive Analysis
AF:小:度量信息论、在线学习和竞争分析
- 批准号:
2007079 - 财政年份:2020
- 资助金额:
$ 23.88万 - 项目类别:
Standard Grant
The analysis of the competitive advantages and global value networks of East Asian ICT companies
东亚ICT企业竞争优势及全球价值网络分析
- 批准号:
19K01913 - 财政年份:2019
- 资助金额:
$ 23.88万 - 项目类别:
Grant-in-Aid for Scientific Research (C)
Analysis of Interruption Risk of Information Diffusion in Consensus Formation based on Bitcoin-like Competitive Information Diffusion
基于类比特币竞争性信息扩散的共识形成过程中信息扩散的中断风险分析
- 批准号:
19KT0045 - 财政年份:2019
- 资助金额:
$ 23.88万 - 项目类别:
Grant-in-Aid for Scientific Research (C)
Competitive Analysis for Incremental Maximization
增量最大化的竞争分析
- 批准号:
413095939 - 财政年份:2019
- 资助金额:
$ 23.88万 - 项目类别:
Research Grants
Collaborative Research: Mathematical and Experimental Analysis of Competitive Ecological Models: Patches, Landscapes, Stage Structure, and Conditional Dispersal on the Boundary
合作研究:竞争性生态模型的数学和实验分析:斑块、景观、阶段结构和边界上的条件扩散
- 批准号:
1853372 - 财政年份:2019
- 资助金额:
$ 23.88万 - 项目类别:
Standard Grant
The Analysis of Retail Store Competitive Advantages : Organizational Capabilities and Store Location
零售商店竞争优势分析:组织能力和商店选址
- 批准号:
19K23231 - 财政年份:2019
- 资助金额:
$ 23.88万 - 项目类别:
Grant-in-Aid for Research Activity Start-up