Zoya Svitkina

Authored Publications
Sort By
  • Title
  • Title, descending
  • Year
  • Year, descending
    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
    Yossi Azar
    Lisa Fleischer
    Kamal Jain
    Operations Research, 63 (2015), pp. 489-500
    Preview
    On Distributing Symmetric Streaming Computations
    S. Muthukrishnan
    Anastasios Sidiropoulos
    Cliff Stein
    Proc. 19th Annual Symposium on Discrete Algorithms (SODA) (2008)
    Preview
    Stochastic Models for Budget Optimization in Search-Based Advertising
    S. Muthukrishnan
    Internet and Network Economics (WINE), Springer, San Diego (2007), pp. 131-142
    Preview