Zoya Svitkina
Research Areas
Authored Publications
Sort By
Preview abstract
In this paper we introduce the semi-online model that generalizes the classical online computational model. The semi-online model postulates that the unknown future has a predictable part and an adversarial part; these parts can be arbitrarily interleaved. An algorithm in this model operates as in the standard online model, i.e., makes an irrevocable decision at each step.
We consider bipartite matching in the semi-online model. Our main contributions are competitive algorithms for this problem and a near-matching hardness bound. The competitive ratio of the algorithms nicely interpolates between the truly offline setting (i.e., no adversarial part) and the truly online setting (i.e., no predictable part).
View details
Preview abstract
In this work we study the problem of using machine-learned predictions to improve performance of online algorithms. We consider two classical problems, ski rental and non-clairvoyant job scheduling, and obtain new online algorithms that use predictions to make their decisions. These algorithms are oblivious to the performance of the predictor, improve with better predictions, but do not degrade much if the predictions are poor.
View details
Optimal Coordination Mechanisms for Unrelated Machine Scheduling
Preview
Yossi Azar
Lisa Fleischer
Kamal Jain
Operations Research, 63 (2015), pp. 489-500
On Distributing Symmetric Streaming Computations
Preview
S. Muthukrishnan
Anastasios Sidiropoulos
Cliff Stein
Proc. 19th Annual Symposium on Discrete Algorithms (SODA) (2008)
Stochastic Models for Budget Optimization in Search-Based Advertising
Preview
S. Muthukrishnan
Internet and Network Economics (WINE), Springer, San Diego (2007), pp. 131-142
