Average-case approximation ratio of scheduling without payments

DOI10.1007/s00453-020-00796-2OpenAlexW2962986620MaRDI QIDQ2032343

Jie Zhang

Publication date: 11 June 2021

Published in: Algorithmica (Search for Journal in Brave)

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)

Related Items (1)

Optimal and Efficient Auctions for the Gradual Procurement of Strategic Service Provider Agents

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Truthful mechanism design for multidimensional scheduling via cycle monotonicity
• The power of verification for one-parameter agents
• Truthful mechanisms for two-range-values variant of unrelated scheduling
• Scheduling without payments
• Winner-imposing strategyproof mechanisms for multiple facility location games
• A lower bound of \(1+\varphi \) for truthful scheduling mechanisms
• Optimal collusion-resistant mechanisms with verification
• Algorithmic mechanism design (extended abstract)
• Bayesian algorithmic mechanism design
• Optimal Lower Bounds for Anonymous Scheduling Mechanisms
• The Double Pareto-Lognormal Distribution—A New Parametric Model for Size Distributions
• A Remark on Stirling's Formula
• Mechanisms with Monitoring for Truthful RAM Allocation
• Algorithmic Game Theory

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