14 citations · 19 across the 11 of their papers we have counts for
12 papers
Truthful Online Scheduling of Cloud Workloads under Uncertainty
Moshe Babaioff, Ronny Lempel, Brendan Lucier +3
Cloud computing customers often submit repeating jobs and computation pipelines on \emph{approximately} regular schedules, with arrival and running times that exhibit variance. Thi…
An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applications
Haotian Jiang, Yin Tat Lee, Zhao Song +1
Given a separation oracle for a convex set that is contained in a box of radius , the goal is to either compute a point in or prove that does no…
Faster Matroid Intersection
Deeparnab Chakrabarty, Yin Tat Lee, Aaron Sidford +2
In this paper we consider the classic matroid intersection problem: given two matroids $\M_{1}=(V,\I_{1})$ and $\M_{2}=(V,\I_{2})$ defined over a common ground set , compute a s…
Network design for s-t effective resistance
Pak Hay Chan, Lap Chi Lau, Aaron Schild +2
We consider a new problem of designing a network with small - effective resistance. In this problem, we are given an undirected graph , two designated vertices $s,t…
Subquadratic Submodular Function Minimization
Deeparnab Chakrabarty, Yin Tat Lee, Aaron Sidford +1
Submodular function minimization (SFM) is a fundamental discrete optimization problem which generalizes many well known problems, has applications in various fields, and can be sol…
Matroid Online Bipartite Matching and Vertex Cover
Yajun Wang, Sam Chiu-wai Wong
The Adwords and Online Bipartite Matching problems have enjoyed a renewed attention over the past decade due to their connection to Internet advertising. Our community has contribu…
Tight Algorithms for Vertex Cover with Hard Capacities on Multigraphs and Hypergraphs
Sam Chiu-wai Wong
In this paper we give a f-approximation algorithm for the minimum unweighted Vertex Cover problem with Hard Capacity constraints (VCHC) on f-hypergraphs. This problem generalizes s…
Tight Bounds for Approximate Carathéodory and Beyond
Vahab Mirrokni, Renato Paes Leme, Adrian Vladu +1
We give a deterministic nearly-linear time algorithm for approximating any point inside a convex polytope with a sparse convex combination of the polytope's vertices. Our result pr…
Computing Walrasian Equilibria: Fast Algorithms and Structural Properties
Renato Paes Leme, Sam Chiu-wai Wong
We present the first polynomial time algorithm for computing Walrasian equilibrium in an economy with indivisible goods and \emph{general} buyer valuations having only access to an…
A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization
Yin Tat Lee, Aaron Sidford, Sam Chiu-wai Wong
We improve upon the running time for finding a point in a convex set given a separation oracle. In particular, given a separation oracle for a convex set co…
Multiplicative Bidding in Online Advertising
MohammadHossein Bateni, Jon Feldman, Vahab Mirrokni +1
In this paper, we initiate the study of the multiplicative bidding language adopted by major Internet search companies. In multiplicative bidding, the effective bid on a particular…
Online Vertex Cover and Matching: Beating the Greedy Algorithm
Yajun Wang, Sam Chiu-wai Wong
In this paper, we explicitly study the online vertex cover problem, which is a natural generalization of the well-studied ski-rental problem. In the online vertex cover problem, we…