Jon Feldman

SODA Conference 2009 Conference Paper

An online mechanism for ad slot reservations with cancellations

• Florin Constantin
• Jon Feldman
• S. Muthukrishnan 0001
• Martin Pál

FOCS Conference 2009 Conference Paper

Online Stochastic Matching: Beating 1-1/e

• Jon Feldman
• Aranyak Mehta
• Vahab Mirrokni
• S. Muthukrishnan 0001

We study the online stochastic bipartite matching problem, in a form motivated by display ad allocation on the Internet. In the online, but adversarial case, the celebrated result of Karp, Vazirani and Vazirani gives an approximation ratio of 1- 1/e ¿ 0. 632, a very familiar bound that holds for many online problems; further, the bound is tight in this case. In the online, stochastic case when nodes are drawn repeatedly from a known distribution, the greedy algorithm matches this approximation ratio, but still, no algorithm is known that beats the 1 - 1/e bound. Our main result is a 0. 67-approximation online algorithm for stochastic bipartite matching, breaking this 1 - ¿ barrier. Furthermore, we show that no online algorithm can produce a 1 - ¿ approximation for an arbitrarily small e for this problem. Our algorithms are based on computing an optimal offline solution to the expected instance, and using this solution as a guideline in the process of online allocation. We employ a novel application of the idea of the power of two choices from load balancing: we compute two disjoint solutions to the expected instance, and use both of them in the online algorithm in a prescribed preference order. To identify these two disjoint solutions, we solve a max flow problem in a boosted flow graph, and then carefully decompose this maximum flow to two edge-disjoint (near-)matchings. In addition to guiding the online decision making, these two offline solutions are used to characterize an upper bound for the optimum in any scenario. This is done by identifying a cut whose value we can bound under the arrival distribution. At the end, we discuss extensions of our results to more general bipartite allocations that are important in a display ad application.

SODA Conference 2008 Conference Paper

On distributing symmetric streaming computations

• Jon Feldman
• S. Muthukrishnan 0001
• Anastasios Sidiropoulos
• Cliff Stein 0001
• Zoya Svitkina

FOCS Conference 2005 Conference Paper

Learning mixtures of product distributions over discrete domains

• Jon Feldman
• Ryan O'Donnell
• Rocco A. Servedio

We consider the problem of learning mixtures of product distributions over discrete domains in the distribution learning framework introduced by Kearns et al. (1994). We give a poly(n//spl epsi/) time algorithm for learning a mixture of k arbitrary product distributions over the n-dimensional Boolean cube {0, 1}/sup n/ to accuracy /spl epsi/, for any constant k. Previous poly(n)-time algorithms could only achieve this for k = 2 product distributions; our result answers an open question stated independently in M. Cryan (1999) and Y. Freund and Y. Mansour (1999). We further give evidence that no polynomial time algorithm can succeed when k is superconstant, by reduction from a notorious open problem in PAC learning. Finally, we generalize our poly(n//spl epsi/) time algorithm to learn any mixture of k = O(1) product distributions over {0, 1, .. ., b }/sup n/, for any b = O(1).

SODA Conference 2005 Conference Paper

LP decoding achieves capacity

• Jon Feldman
• Cliff Stein 0001

FOCS Conference 2002 Conference Paper

Decoding Turbo-Like Codes via Linear Programming

• Jon Feldman
• David R. Karger

We introduce a novel algorithm for decoding turbo-like codes based on linear programming. We prove that for the case of repeat-accumulate (RA) codes, under the binary symmetric channel with a certain constant threshold bound on the noise, the error probability of our algorithm is bounded by an inverse polynomial in the code length. Our linear program (LP) minimizes the distance between the received bits and binary variables representing the code bits. Our LP is based on a representation of the code where code words are paths through a graph. Consequently, the LP bears a strong resemblance to the min-cost flow LP. The error bounds are based on an analysis of the probability, over the random noise of the channel, that the optimum solution to the LP is the path corresponding to the original transmitted code word.

SODA Conference 2001 Conference Paper

Parallel processor scheduling with delay constraints

• Daniel W. Engels
• Jon Feldman
• David R. Karger
• Matthias Ruhl

FOCS Conference 1999 Conference Paper

The Directed Steiner Network Problem is Tractable for a Constant Number of Terminals

• Jon Feldman
• Matthias Ruhl

We consider the Directed Steiner Network (DSN) problem, also called the Point-to-Point Connection problem, where given a directed graph G and p pairs {(s/sub 1/, t/sub 1/), .. ., (s/sub p/, t/sub p/)} of nodes in the graph, one has to find the smallest subgraph H of G that contains paths from s/sub i/ to t/sub i/ for all i. The problem is NP-hard for general p, since the Directed Steiner Tree problem is a special case. Until now, the complexity was unknown for constant p/spl ges/3. We prove that the problem is polynomially solvable if p is any constant number, even if nodes and edges in G are weighted and the goal is to minimize the total weight of the subgraph H. In addition, we give an efficient algorithm for the Strongly Connected Steiner Subgraph problem for any constant p, where given a directed graph and p nodes in the graph, one has to compute the smallest strongly connected subgraph containing the p nodes.