Algorithms - Microsoft Research

Video

Strong LP Formulations and Primal-Dual Approximation Algorithms

June 1, 2011 | David Shmoys

The state of the art of the design and analysis of approximation algorithms for NP-hard discrete optimization has advanced significantly over the past two decades; furthermore, the most prevalent approach has been to rely on…

01:06:09

Publication

Understanding how both the partitions of a bipartite network affect its one-mode projection

Animesh Mukherjee, Monojit Choudhury, Niloy Ganguly

Physica A: Statistical Mechanics and its Applications | June 2011, Vol 390(20): pp. 3602-3607

Publication

Distributed Algorithms via Gradient Descent for Fisher Markets

Benjamin Birnbaum, Nikhil Devanur, Lin Xiao

Proceedings of the 12th ACM Conference on Electronic Commerce | June 2011

Publication

Learning Time-Based Presence Probabilities

John Krumm, A.J. Brush

Pervasive 2011 | June 2011

Project

Publication

On Approximating the Entropy of Polynomial Mappings

Zeev Dvir, Dan Gutfreund, Guy Rothblum, Salil Vadhan

Proceedings of The Second Symposium on Innovations in Computer Science (ICS 2011), ICS | June 2011

ICS

Publication

Stochastic Variability in Sponsored Search Auctions: Observations and Models

Furcy Pin, Peter Key

EC11: 12th ACM Conference on Electronic Commerce | June 2011

Publication

Optimal Multi-Period Pricing with Service Guarantees

Christian Borgs, Jennifer Chayes, Ozan Candogan, Ilan Lobel, Hamid Nazer Zadeh

MSR-TR-2011-77 | June 2011

Publication

Online Algorithms with Stochastic Input

Nikhil Devanur

June 2011, Vol 10: pp. 40-49

In ACM SIGEcom Exchanges

Publication

Detail-free, Posted-Price Mechanisms for Limited Supply Online Auctions

Moshe Babaioff, Shaddin Dughmi, Aleksandrs Slivkins

Workshop on Bayesian Mechanism Design | June 2011

Publication

Resilience of Mutual Exclusion Algorithms to Transient Memory Faults

Thomas Moscibroda, Rotem Oshman

30th Annual Symposium on Principles of Distributed Computing (PODC) | June 2011