12 citations · 38 across the 15 of their papers we have counts for
4 papers · 1 filter
Tighter bounds for online bipartite matching
Uriel Feige
We study the online bipartite matching problem, introduced by Karp, Vazirani and Vazirani [1990]. For bipartite graphs with matchings of size , it is known that the Ranking rand…
Finding cliques using few probes
Uriel Feige, David Gamarnik, Joe Neeman +2
Consider algorithms with unbounded computation time that probe the entries of the adjacency matrix of an vertex graph, and need to output a clique. We show that if the input gr…
A Polynomial Time Constant Approximation For Minimizing Total Weighted Flow-time
Uriel Feige, Janardhan Kulkarni, Shi Li
We consider the classic scheduling problem of minimizing the total weighted flow-time on a single machine (min-WPFT), when preemption is allowed. In this problem, we are given a se…
Max-Min Greedy Matching
Alon Eden, Uriel Feige, Michal Feldman
A bipartite graph that admits a perfect matching is given. One player imposes a permutation over , the other player imposes a permutation over . In the gre…