10 citations · 11 across the 4 of their papers we have counts for
5 papers
A Distributed Approximation Algorithm for the Metric Uncapacitated Facility Location Problem in the Congest Model
Patrick Briest, Bastian Degener, Barbara Kempkes +2
We present a randomized distributed approximation algorithm for the metric uncapacitated facility location problem. The algorithm is executed on a bipartite graph in the Congest mo…
Improved Hardness of Approximation for Stackelberg Shortest-Path Pricing
Patrick Briest, Sanjeev Khanna
We consider the Stackelberg shortest-path pricing problem, which is defined as follows. Given a graph G with fixed-cost and pricable edges and two distinct vertices s and t, we may…
Pricing Randomized Allocations
Patrick Briest, Shuchi Chawla, Robert Kleinberg +1
Randomized mechanisms, which map a set of bids to a probability distribution over outcomes rather than a single outcome, are an important but ill-understood area of computational m…
Approximate Equilibria in Games with Few Players
Patrick Briest, Paul W. Goldberg, Heiko Roeglin
We study the problem of computing approximate Nash equilibria (epsilon-Nash equilibria) in normal form games, where the number of players is a small constant. We consider the appro…
Stackelberg Network Pricing Games
Patrick Briest, Martin Hoefer, Piotr Krysta
We study a multi-player one-round game termed Stackelberg Network Pricing Game, in which a leader can set prices for a subset of priceable edges in a graph. The other edges hav…