95 citations · 767 across the 72 of their papers we have counts for
Showing 2006Show all
2 papers · 1 filter
cs.GT2006
Frugality ratios and improved truthful mechanisms for vertex cover
Edith Elkind, Leslie Ann Goldberg, Paul W. Goldberg
In {\em set-system auctions}, there are several overlapping teams of agents, and a task that can be completed by any of these teams. The buyer's goal is to hire a team and pay as l…
cs.CC2006★ 74 cited
Inapproximability of the Tutte polynomial
Leslie Ann Goldberg, Mark Jerrum
The Tutte polynomial of a graph G is a two-variable polynomial T(G;x,y) that encodes many interesting properties of the graph. We study the complexity of the following problem, for…