Consensus Division in an Arbitrary Ratio
summary
Shows that for alpha = l/k rationals worst-case lower bound is about 2(k−1)/k · n cuts and gives matching upper bounds for a large subset Q of rationals, while other rationals admit an upper bound C_alpha · n with C_alpha < 2. Equates imbalanced consensus division with necklace splitting, proves membership results: many exact-bound cases lie in PPA-k (and in PPA-p when p divides k), 2n cuts give PPA membership, 8n yields PPA-3, n log n makes the task polynomial, and finding an instance-optimal cut count is NP-hard.
AI-written summary · about
chapters (12)
- 0:00Introduction
- 0:18Lucky Splitting
- 0:45Even Splitting
- 2:30Natural Transition
- 3:53Causative
- 5:27In imbalanced
- 9:33Consistent Division
- 11:05Results
- 12:38Upper Bounds
- 14:38Complexity
- 20:21Reduction
- 21:59Other problems
related talks
20mBalanced Allocations with Incomplete Information: The Power of Two Queries
10mQuery, Communication and Discrepancy
01h 20mAn Introduction to Distributed, Massively Parallel, and Local Computation Algorithms
26mCounting Distinct Elements in the Message Passing Model
18mEqual Opportunity: A Correctness Condition for Ordered Consensus
30mDistributed Statistical Estimation of Matrix Products with Applications
40mConsensus Algorithms in Distributed Systems
48mDistributed Consensus Algorithms