Beyond the worst-case analysis of random priority: smoothed and average-case approximation ratios in mechanism design (Q2672280): Difference between revisions

@@ Property / cites work @@
+Random Serial Dictatorship and the Core from Random Endowments in House Allocation Problems
+Normal rank
@@ Property / cites work @@
+House allocation with existing tenants
@@ Property / cites work: House allocation with existing tenants / rank @@
+Normal rank
@@ Property / cites work @@
+Approximating optimal social choice under metric preferences
+Normal rank
@@ Property / cites work @@
+Q4471296
@@ Property / cites work: Q4471296 / rank @@
+Normal rank
@@ Property / cites work @@
+Worst-Case and Smoothed Analysis of the ICP Algorithm, with an Application to the k-Means Method
+Normal rank
@@ Property / cites work @@
+The computational complexity of random serial dictatorship
+Normal rank
@@ Property / cites work @@
+Mathematical Foundations of Computer Science 2003
@@ Property / cites work: Mathematical Foundations of Computer Science 2003 / rank @@
+Normal rank
@@ Property / cites work @@
+Social Welfare in One-Sided Matching Markets without Money
+Normal rank
@@ Property / cites work @@
+Smoothed analysis of partitioning algorithms for Euclidean functionals
+Normal rank
@@ Property / cites work @@
+Q4829029
@@ Property / cites work: Q4829029 / rank @@
+Normal rank
@@ Property / cites work @@
+A new solution to the random assignment problem.
@@ Property / cites work: A new solution to the random assignment problem. / rank @@
+Normal rank
@@ Property / cites work @@
+The Average number of pivot steps required by the Simplex-Method is polynomial
+Normal rank
@@ Property / cites work @@
+Stochastic Mean Payoff Games: Smoothed Analysis and Approximation Schemes
+Normal rank
@@ Property / cites work @@
+Settling the complexity of computing two-player Nash equilibria
+Normal rank
@@ Property / cites work @@
+Truth, justice, and cake cutting
@@ Property / cites work: Truth, justice, and cake cutting / rank @@
+Normal rank
@@ Property / cites work @@
+A lower bound for scheduling mechanisms
@@ Property / cites work: A lower bound for scheduling mechanisms / rank @@
+Normal rank
@@ Property / cites work @@
+Q3651735
@@ Property / cites work: Q3651735 / rank @@
+Normal rank
@@ Property / cites work @@
+Q5111230
@@ Property / cites work: Q5111230 / rank @@
+Normal rank
@@ Property / cites work @@
+Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP
+Normal rank
@@ Property / cites work @@
+Social Welfare in One-Sided Matchings: Random Priority and Beyond
+Normal rank
@@ Property / cites work @@
+On smoothed analysis of quicksort and Hoare's find
+Normal rank
@@ Property / cites work @@
+Bayesian algorithmic mechanism design
@@ Property / cites work: Bayesian algorithmic mechanism design / rank @@
+Normal rank
@@ Property / cites work @@
+A solution to the random assignment problem on the full preference domain
+Normal rank
@@ Property / cites work @@
+Why do popular mechanisms lack efficiency in random environments?
+Normal rank
@@ Property / cites work @@
+Scheduling without payments
@@ Property / cites work: Scheduling without payments / rank @@
+Normal rank
@@ Property / cites work @@
+Smoothed analysis of binary search trees
@@ Property / cites work: Smoothed analysis of binary search trees / rank @@
+Normal rank
@@ Property / cites work @@
+Truthful approximation mechanisms for restricted combinatorial auctions
+Normal rank
@@ Property / cites work @@
+Q5844986
@@ Property / cites work: Q5844986 / rank @@
+Normal rank
@@ Property / cites work @@
+Algorithmic mechanism design (extended abstract)
@@ Property / cites work: Algorithmic mechanism design (extended abstract) / rank @@
+Normal rank
@@ Property / cites work @@
+Algorithmic Game Theory
@@ Property / cites work: Algorithmic Game Theory / rank @@
+Normal rank
@@ Property / cites work @@
+Lotteries in student assignment: An equivalence result
+Normal rank
@@ Property / cites work @@
+Q3999327
@@ Property / cites work: Q3999327 / rank @@
+Normal rank
@@ Property / cites work @@
+Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices
+Normal rank
@@ Property / cites work @@
+Topology matters: smoothed competitiveness of metrical task systems
+Normal rank
@@ Property / cites work @@
+Smoothed analysis of algorithms
@@ Property / cites work: Smoothed analysis of algorithms / rank @@
+Normal rank
@@ Property / cites work @@
+Smoothed analysis of termination of linear programming algorithms
+Normal rank
@@ Property / cites work @@
+Strategy-proof allocation of indivisible goods
@@ Property / cites work: Strategy-proof allocation of indivisible goods / rank @@
+Normal rank
@@ Property / cites work @@
+On a conjecture by Gale about one-sided matching problems
+Normal rank