Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

University of Toronto

$48,000.00

Design, Analysis, and Theory of Algorithms, and Applcations

EF 2024-25

Résumé
My main research focus concerns the design, analysis and theory of algorithmic paradigms with emphasis on "conceptually simple algorithms". I have a long term interest in online, and greedy-like algorithms. I use the term "online algorithms" in the broad sense of ``myopic algorithms'' that have no control over the sequence of future online arrivals. In this larger context, the field is experiencing a burst of activity due to many reasons: more general online models (e.g. revocable decisions, delayed decisions, multiple passes, parallel online algorithms, untrusted advice and predictions), more restricted online models (bounded memory or bounded randomization), random order arrivals and stochastic input sequences, many new applications (the taxi problem, bandwidth problems, fair allocation), new algorithmic ideas (contention resolution schemes and online correlated schemes), and recent progress on long standing open problems (the randomized $k$-server and MTS conjectures, edge weighted bipartite matching). Beyond online algorithms (having no control over the future sequence of online requests), I view greedy algorithms as myopic algorithms in the sense that greedy algorithms enjoy a restricted way in which the sequence of request arrivals can be ordered without fully revealing the future (as formalized by what are called priority algorithms). The extensions and extensions of online algorithms mentioned above can be applied to greedy algorithms providing a rich palette of conceptually simple algorithms. I also include local search as another example of a conceptual simple algorithmic paradigm. The benefit of such conceptually simple paradigms is that they can be easily implemented, often provide results that are competitive with the best known offline algorithms, often reflect application requirements, and may be successfully analyzed without being subject to the current limitations in our understanding of the fundamental questions in complexity theory. Simplicity may also be considered necessary when inputs are being provided by individuals. Conceptual simplicity has led me to issues in computational social choice (e.g., voting and fair division) and algorithmic mechanism design (e.g., auctions). In these areas, we should assume that individuals and groups are self interested which leads to issues of fairness, privacy, truthfulness, stability).  While such issues are actively studied in computational social choice, and algorithmic game theory for both arbitrary offline algorithms and online algorithms, there has been little attention to other conceptually simple algorithmic paradigms as mentioned above. An interesting relatively new research direction is to consider online algorithms with predictions, where we want improved performance with small prediction error and robust (i.e. performance not significantly degraded) with large error. Is there a relation between truthful mechanisms and algorithms with predictions?
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
RGPIN-2024-05682
Name nom
Borodin, Allan
Department département
Computer Science
Organization id
31
Institution établissement
University of Toronto
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2024
Competition year année de concours
2024
Award amount
48000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
1205
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Mathematical sciences
Area of application fr
Sciences mathématiques
Research subject code
2713
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Algorithms
Research subject fr
Algorithmes
Field of research list names en
Not available
Field of research list names fr
Non disponible
Socioeconomic objective list names en
Not available
Socioeconomic objective list names fr
Non disponible
Application title
Design, Analysis, and Theory of Algorithms, and Applcations
Keywords
greedy algorithms; online algorithms; algorithmic paradigms; myopic algorithms; stochastic optimization; mechanism design; voting; fair allocation; social choice
Application summary
My main research focus concerns the design, analysis and theory of algorithmic paradigms with emphasis on "conceptually simple algorithms". I have a long term interest in online, and greedy-like algorithms. I use the term "online algorithms" in the broad sense of ``myopic algorithms'' that have no control over the sequence of future online arrivals. In this larger context, the field is experiencing a burst of activity due to many reasons: more general online models (e.g. revocable decisions, delayed decisions, multiple passes, parallel online algorithms, untrusted advice and predictions), more restricted online models (bounded memory or bounded randomization), random order arrivals and stochastic input sequences, many new applications (the taxi problem, bandwidth problems, fair allocation), new algorithmic ideas (contention resolution schemes and online correlated schemes), and recent progress on long standing open problems (the randomized $k$-server and MTS conjectures, edge weighted bipartite matching). Beyond online algorithms (having no control over the future sequence of online requests), I view greedy algorithms as myopic algorithms in the sense that greedy algorithms enjoy a restricted way in which the sequence of request arrivals can be ordered without fully revealing the future (as formalized by what are called priority algorithms). The extensions and extensions of online algorithms mentioned above can be applied to greedy algorithms providing a rich palette of conceptually simple algorithms. I also include local search as another example of a conceptual simple algorithmic paradigm. The benefit of such conceptually simple paradigms is that they can be easily implemented, often provide results that are competitive with the best known offline algorithms, often reflect application requirements, and may be successfully analyzed without being subject to the current limitations in our understanding of the fundamental questions in complexity theory. Simplicity may also be considered necessary when inputs are being provided by individuals. Conceptual simplicity has led me to issues in computational social choice (e.g., voting and fair division) and algorithmic mechanism design (e.g., auctions). In these areas, we should assume that individuals and groups are self interested which leads to issues of fairness, privacy, truthfulness, stability).  While such issues are actively studied in computational social choice, and algorithmic game theory for both arbitrary offline algorithms and online algorithms, there has been little attention to other conceptually simple algorithmic paradigms as mentioned above. An interesting relatively new research direction is to consider online algorithms with predictions, where we want improved performance with small prediction error and robust (i.e. performance not significantly degraded) with large error. Is there a relation between truthful mechanisms and algorithms with predictions?