Average-case approximation ratio of scheduling without payments

DOI10.1007/S00453-020-00796-2MaRDI QIDQ2032343zbMATH OpenOpenAlexFDO

Authors Jie Zhang

Publication date 11 June 2021

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1711.06937

zbMATH Keywords

schedulingaverage-case analysisapproximation ratio

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Recommendations

• Smoothed and average-case approximation ratios of mechanisms: beyond the worst-case analysis
• Scheduling without payments
• A lower bound for scheduling mechanisms
• Scheduling without payments
• A lower bound for scheduling mechanisms

Cites work

• A Remark on Stirling's Formula
• A lower bound of \(1+\varphi \) for truthful scheduling mechanisms
• Algorithmic Game Theory
• Algorithmic mechanism design (extended abstract)
• An improved randomized truthful mechanism for scheduling unrelated machines
• Bayesian algorithmic mechanism design
• Mechanisms with monitoring for truthful RAM allocation
• Optimal collusion-resistant mechanisms with verification
• Optimal lower bounds for anonymous scheduling mechanisms
• Scheduling without payments
• Setting lower bounds on truthfulness (extended abstract)
• Smoothed and average-case approximation ratios of mechanisms: beyond the worst-case analysis
• The Double Pareto-Lognormal Distribution—A New Parametric Model for Size Distributions
• The power of verification for one-parameter agents
• Truthful mechanism design for multidimensional scheduling via cycle monotonicity
• Truthful mechanisms for two-range-values variant of unrelated scheduling
• Winner-imposing strategyproof mechanisms for multiple facility location games

Cited in

(3)

• Optimal and Efficient Auctions for the Gradual Procurement of Strategic Service Provider Agents
• Smoothed and average-case approximation ratios of mechanisms: beyond the worst-case analysis
• On scheduling mechanisms beyond the worst case

This page was built for publication: Average-case approximation ratio of scheduling without payments

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2032343)