42 citations · 50 across the 6 of their papers we have counts for
6 papers
Sponsored Search Auctions with Rich Ads
Ruggiero Cavallo, Prabhakar Krishnamurthy, Maxim Sviridenko +1
The generalized second price (GSP) auction has served as the core selling mechanism for sponsored search ads for over a decade. However, recent trends expanding the set of allowed…
Polynomial-Time Approximation Schemes for Circle and Other Packing Problems
Flávio K. Miyazawa, Lehilton L. C. Pedrosa, Rafael C. S. Schouery +2
We give an asymptotic approximation scheme (APTAS) for the problem of packing a set of circles into a minimum number of unit square bins. To obtain rational solutions, we use augme…
An Algorithm for Online K-Means Clustering
Edo Liberty, Ram Sriharsha, Maxim Sviridenko
This paper shows that one can be competitive with the k-means objective while operating online. In this model, the algorithm receives vectors v_1,...,v_n one by one in an arbitrary…
Optimization Problems with Diseconomies of Scale via Decoupling
Konstantin Makarychev, Maxim Sviridenko
We present a new framework for solving optimization problems with a diseconomy of scale. In such problems, our goal is to minimize the cost of resources used to perform a certain t…
Maximum Quadratic Assignment Problem: Reduction from Maximum Label Cover and LP-based Approximation Algorithm
Konstantin Makarychev, Rajsekar Manokaran, Maxim Sviridenko
We show that for every positive , unless NP BPQP, it is impossible to approximate the maximum quadratic assignment problem within a factor better than $2^{\log^{1-ε…
Energy Efficient Scheduling and Routing via Randomized Rounding
Evripidis Bampis, Alexander Kononov, Dimitrios Letsios +2
We propose a unifying framework based on configuration linear programs and randomized rounding, for different energy optimization problems in the dynamic speed-scaling setting. We…