Research map / Learning theory and algorithms / Submodular and game algorithms
Efficient Truthful Scheduling and Resource Allocation through Monitoring
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use an MIR allocation with a non-decreasing 1-Lipschitz objective | VCGmon · General cost minimization problems | truthfulness | Helped |
| Use randomized rounding of the LP solution for restricted-related machines | VCGmon · Restricted-related machines, makespan | approximation ratio: 2-approximate | Helped |
| Apply the LP-based fractional mechanism with parameter pruning to unrelated machines | VCGmon · Unrelated machines, makespan | truthfulness | Hurt |
| Apply VCGmon using Hochbaum and Shmoys' generic bottleneck algorithm | Bottleneck network optimization · Bottleneck network optimization problems | truthfulness | Helped |
| Extend the bottleneck algorithm to agents owning multiple edges | VCGmon with the generic bottleneck algorithm · Bottleneck network optimization | truthfulness | Hurt |
| Use a deterministic approximation algorithm for binary covering with social cost | VCGmon · Binary covering problems | truthfulness: α-truthful | Helped |
| Use a deterministic approximation algorithm with ratio greater than 1 for a strictly all-monotone objective | Truthful VCGmon · Binary covering problems | approximation ratio: 1+ε | Hurt |
Closest papers by meaning
- Parsimonious Predictions for Strategyproof Scheduling (NeurIPS 2025 · similarity 0.86)
- Differentiable Combinatorial Scheduling at Scale (ICML 2024 · similarity 0.84)
- Plant-and-Steal: Truthful Fair Allocations via Predictions (NeurIPS 2024 · similarity 0.83)
- Approximation algorithms for combinatorial optimization with predictions (ICLR 2025 · similarity 0.83)
- A Unified Framework for Uniform-Price Resource Allocation Mechanisms (NeurIPS 2026 · similarity 0.83)
- Non-clairvoyant Scheduling with Partial Predictions (ICML 2024 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.