Smoothed and average-case approximation ratios of mechanisms: beyond the worst-case analysis
From MaRDI portal
Publication:5111230
Recommendations
- Beyond the worst-case analysis of random priority: smoothed and average-case approximation ratios in mechanism design
- Average-case approximation ratio of scheduling without payments
- Social welfare in one-sided matchings: random priority and beyond
- Size versus truncation robustness in the assignment problem
- Black-box randomized reductions in algorithmic mechanism design
Cites work
- scientific article; zbMATH DE number 5145289 (Why is no real title available?)
- scientific article; zbMATH DE number 2079341 (Why is no real title available?)
- scientific article; zbMATH DE number 2119754 (Why is no real title available?)
- scientific article; zbMATH DE number 3084669 (Why is no real title available?)
- A Lower Bound of 1 + φ for Truthful Scheduling Mechanisms
- A lower bound for scheduling mechanisms
- A new solution to the random assignment problem.
- Algorithmic Game Theory
- Algorithmic mechanism design
- Algorithmic mechanism design (extended abstract)
- An introduction to strategy-proof social choice functions
- Average-Case and Smoothed Competitive Analysis of the Multilevel Feedback Algorithm
- Bayesian algorithmic mechanism design
- Introduction to algorithms.
- Lotteries in student assignment: an equivalence result
- Mathematical Foundations of Computer Science 2003
- Mix and match: a strategyproof mechanism for multi-hospital kidney exchange
- On a conjecture by Gale about one-sided matching problems
- On smoothed analysis of quicksort and Hoare's find
- Optimal auctions vs. anonymous pricing
- Partial strategyproofness: relaxing strategyproofness for the random assignment problem
- Random Serial Dictatorship and the Core from Random Endowments in House Allocation Problems
- Scheduling without payments
- Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices
- Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time
- Smoothed analysis of binary search trees
- Smoothed analysis of partitioning algorithms for Euclidean functionals
- Smoothed analysis of termination of linear programming algorithms
- Social welfare in one-sided matchings: random priority and beyond
- Stochastic mean payoff games: smoothed analysis and approximation schemes
- Strategy-proof allocation of indivisible goods
- The Average number of pivot steps required by the Simplex-Method is polynomial
- The Impossibility of Bayesian Group Decision Making with Separate Aggregation of Beliefs and Values
- Topology matters: smoothed competitiveness of metrical task systems
- Truth revelation in approximately efficient combinatorial auctions
- Truthful approximation mechanisms for restricted combinatorial auctions
- Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP
- Worst-case and smoothed analysis of the ICP algorithm, with an application to the k-means method
Cited in
(3)
This page was built for publication: Smoothed and average-case approximation ratios of mechanisms: beyond the worst-case analysis
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111230)
