908 citations · 918 across the 17 of their papers we have counts for
19 papers
Dynamics and Inference for Voter Model Processes
Milan Vojnovic, Kaifang Zhou
We consider a discrete-time voter model process on a set of nodes, each being in one of two states, either 0 or 1. In each time step, each node adopts the state of a randomly sampl…
On Regret-optimal Cooperative Nonstochastic Multi-armed Bandits
Jialin Yi, Milan Vojnović
We consider the nonstochastic multi-agent multi-armed bandit problem with agents collaborating via a communication network with delays. We show a lower bound for individual regret…
Rotting Infinitely Many-armed Bandits
Jung-hun Kim, Milan Vojnovic, Se-Young Yun
We consider the infinitely many-armed bandit problem with rotting rewards, where the mean reward of an arm decreases at each pull of the arm according to an arbitrary trend with ma…
Learning to Schedule in Parallel-Server Queues with Stochastic Bilinear Rewards
Jung-hun Kim, Milan Vojnovic
We consider the problem of scheduling in multi-class, parallel-server queuing systems with uncertain rewards from job-server assignments. In this scenario, jobs incur holding costs…
Pure Exploration and Regret Minimization in Matching Bandits
Flore Sentenac, Jialin Yi, Clément Calauzènes +2
Finding an optimal matching in a weighted graph is a standard combinatorial problem. We consider its semi-bandit version where either a pair or a full matching is sampled sequentia…
Scheduling Jobs with Stochastic Holding Costs
Dabeen Lee, Milan Vojnovic
We study a single-server scheduling problem for the objective of minimizing the expected cumulative holding cost incurred by jobs, where parameters defining stochastic job holding…
Test Score Algorithms for Budgeted Stochastic Utility Maximization
Dabeen Lee, Milan Vojnovic, Se-Young Yun
Motivated by recent developments in designing algorithms based on individual item scores for solving utility maximization problems, we study the framework of using test scores, def…
Popularity Prediction for Social Media over Arbitrary Time Horizons
Daniel Haimovich, Dima Karamshuk, Thomas J. Leeper +2
Predicting the popularity of social media content in real time requires approaches that efficiently operate at global scale. Popularity prediction is important for many application…
Accelerated MM Algorithms for Ranking Scores Inference from Comparison Data
Milan Vojnovic, Seyoung Yun, Kaifang Zhou
In this paper, we study a popular method for inference of the Bradley-Terry model parameters, namely the MM algorithm, for maximum likelihood estimation and maximum a posteriori pr…
KONG: Kernels for ordered-neighborhood graphs
Moez Draief, Konstantin Kutzkov, Kevin Scaman +1
We present novel graph kernels for graphs with node and edge labels that have ordered neighborhoods, i.e. when neighbor nodes follow an order. Graphs with ordered neighborhoods are…
Parameter Estimation for Thurstone Choice Models
Milan Vojnovic, Se-Young Yun
We consider the estimation accuracy of individual strength parameters of a Thurstone choice model when each input observation consists of a choice of one item from a set of two or…
Communication complexity of approximate maximum matching in the message-passing model
Zengfeng Huang, Bozidar Radunovic, Milan Vojnovic +1
We consider the communication complexity of finding an approximate maximum matching in a graph in a multi-party message-passing communication model. The maximum matching problem is…
Adaptive Matching for Expert Systems with Uncertain Task Types
Virag Shah, Lennart Gulikers, Laurent Massoulie +1
A matching in a two-sided market often incurs an externality: a matched resource may become unavailable to the other side of the market, at least for a while. This is especially an…
QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding
Dan Alistarh, Demjan Grubic, Jerry Li +2
Parallel implementations of stochastic gradient descent (SGD) have received significant research attention, thanks to excellent scalability properties of this algorithm, and to its…
Submodular Maximization using Test Scores
Shreyas Sekar, Milan Vojnovic, Se-Young Yun
We study the canonical problem of maximizing a stochastic submodular function subject to a cardinality constraint, where the goal is to select a subset from a ground set of items w…
Spectral Ranking using Seriation
Fajwel Fogel, Alexandre d'Aspremont, Milan Vojnovic
We describe a seriation algorithm for ranking a set of items given pairwise comparisons between these items. Intuitively, the algorithm assigns similar rankings to items that compa…
Incentives and Efficiency in Uncertain Collaborative Environments
Yoram Bachrach, Vasilis Syrgkanis, Milan Vojnovic
We consider collaborative systems where users make contributions across multiple available projects and are rewarded for their contributions in individual projects according to a l…
Strong Price of Anarchy and Coalitional Dynamics
Yoram Bachrach, Vasilis Syrgkanis, Eva Tardos +1
We introduce a framework for studying the effect of cooperation on the quality of outcomes in utility games. Our framework is a coalitional analog of the smoothness framework of no…
Bargaining Dynamics in Exchange Networks
Moez Draief, Milan Vojnovic
We consider a dynamical system for computing Nash bargaining solutions on graphs and focus on its rate of convergence. More precisely, we analyze the edge-balanced dynamical system…