Research map / Learning theory and algorithms / Submodular and game algorithms
Contiguous Cake Cutting: Hardness Results and Approximation Algorithms
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 the moving-knife allocation algorithm for arbitrary valuations | Contiguous cake cutting · General valuations | maximum additive envy: 1/3 | Helped |
| Use the interval-specific algorithm, processing agents by increasing valued-interval length | Contiguous cake cutting · Piecewise uniform, single-interval valuations | maximum additive envy: 1/4 | Helped |
| Require agent 1 to receive the leftmost piece | Contiguous envy-free cake cutting with piecewise uniform valuations · Continuous cake cutting | computational complexity of deciding existence | Hurt |
| Fix the ordering of agents from left to right | Contiguous envy-free cake cutting with piecewise uniform valuations · Continuous cake cutting | computational complexity of deciding existence | Hurt |
| Require a cut at a specified position | Contiguous envy-free cake cutting with piecewise uniform valuations · Continuous cake cutting | computational complexity of deciding existence | Hurt |
| Restrict item valuations to binary while requiring agents to value the same number of items | Contiguous allocation of indivisible items · Linearly ordered items; envy-freeness, proportionality, or equitability | computational complexity of deciding existence | Hurt |
| Require every agent to value one contiguous block of binary-valued items | Contiguous allocation of indivisible items · Proportionality | computational complexity of deciding existence | Hurt |
| Allow approximate rather than exact envy-freeness | Contiguous allocation of indivisible items with binary valuations and equal numbers of valued items · Discrete cake cutting | computational complexity of deciding existence: ε < 1/13 | No clear effect |
| Replace exact envy-freeness with sufficiently small approximate envy-freeness | Contiguous cake cutting with piecewise constant valuations · Continuous cake cutting | computational complexity of finding an allocation: M^{-20kn} | No clear effect |
Closest papers by meaning
- On Hierarchies of Fairness Notions in Cake Cutting: From Proportionality to Super Envy-Freeness (NeurIPS 2025 · similarity 0.93)
- Fair Division via the Cake-Cutting Share (AAAI 2025 · similarity 0.91)
- The Complexity of Extending Fair Allocations of Indivisible Goods (AAAI 2025 · similarity 0.90)
- Envy-Free House Allocation under Uncertain Preferences (AAAI 2024 · similarity 0.88)
- Almost Envy-Free Allocations of Indivisible Goods or Chores with Entitlements (AAAI 2024 · similarity 0.88)
- The Complexity of Fair Division of Indivisible Items with Externalities (AAAI 2024 · similarity 0.88)
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.