Copertina

An $Ω(n \log n)$ Randomized Lower Bound for Cutting a Cake into Proportionally Fair Pieces

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Arndt, Stephen, Pruhs, Kirk, Tran, Trung
Natura:	Preprint
Pubblicazione:	2026
Soggetti:	Data Structures and Algorithms Discrete Mathematics
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Multi-Pass Streaming Lower Bounds for Approximating Max-Cut
di: Fei, Yumou, et al.
Pubblicazione: (2025)

A Lower Bound on the Competitive Ratio of the Permutation Algorithm for Online Facility Assignment on a Line
di: Harada, Tsubasa
Pubblicazione: (2024)

An approximation algorithm for Maximum DiCut vs. Cut
di: Nakajima, Tamio-Vesa, et al.
Pubblicazione: (2024)

Path Contraction Faster than $2^n$
di: Agrawal, Akanksha, et al.
Pubblicazione: (2025)

On the Bidirected Cut Relaxation for Steiner Forest
di: Byrka, Jarosław, et al.
Pubblicazione: (2024)

Tight Bounds for Sparsifying Random CSPs
di: Brakensiek, Joshua, et al.
Pubblicazione: (2025)

Circulant TSP: Vertices of the Edge-Length Polytope and Superpolynomial Lower Bounds
di: Gutekunst, Samuel C.
Pubblicazione: (2025)

Lower Bounds for Linear Operators
di: Ko, Young Kun
Pubblicazione: (2025)

The Parameterized Complexity Landscape of Two-Sets Cut-Uncut
di: Bentert, Matthias, et al.
Pubblicazione: (2024)

Fairness in Repetitive Scheduling
di: Hermelin, Danny, et al.
Pubblicazione: (2021)

Space-Efficient Hierholzer: Eulerian Cycles in $\mathrm{O}(m)$ Time and $\mathrm{O}(n)$ Space
di: Alaoui, Ziad Ismaili, et al.
Pubblicazione: (2025)

The Bidirected Cut Relaxation for Steiner Tree has Integrality Gap Smaller than 2
di: Byrka, Jarosław, et al.
Pubblicazione: (2024)

Improved Streaming Algorithm for Fair $k$-Center Clustering
di: Guo, Longkun, et al.
Pubblicazione: (2025)

Cutwidth Bounds via Vertex Partitions
di: Amarilli, Antoine, et al.
Pubblicazione: (2025)

Temporal Graph Realization With Bounded Stretch
di: Mertzios, George B., et al.
Pubblicazione: (2025)

Cuts and Gauges for Submodular Width
di: Lanzinger, Matthias
Pubblicazione: (2026)

Cuts in Graphs with Matroid Constraints
di: Banik, Aritra, et al.
Pubblicazione: (2024)

Linear-Time MaxCut in Multigraphs Parameterized Above the Poljak-Turzík Bound
di: Lill, Jonas, et al.
Pubblicazione: (2024)

Nearly Tight Bounds on Testing of Metric Properties
di: Bao, Yiqiao, et al.
Pubblicazione: (2024)

Optimal Padded Decomposition For Bounded Treewidth Graphs
di: Filtser, Arnold, et al.
Pubblicazione: (2024)

Maximizing a Submodular Function with Bounded Curvature under an Unknown Knapsack Constraint
di: Klimm, Max, et al.
Pubblicazione: (2022)

Bounding $\varepsilon$-scatter dimension via metric sparsity
di: Bourneuf, Romain, et al.
Pubblicazione: (2024)

Subgraph Counting in Subquadratic Time for Bounded Degeneracy Graphs
di: Paul-Pena, Daniel, et al.
Pubblicazione: (2024)

Lower Bounds on the Complexity of Mixed-Integer Programs for Stable Set and Knapsack
di: Schade, Jamico, et al.
Pubblicazione: (2023)

Efficient Algorithms for Interdicting Facilities in Trees and Bounded Treewidth Graphs
di: Abbasi, Ali, et al.
Pubblicazione: (2026)

Unsplittable Cost Flows from Unweighted Error-Bounded Variants
di: Swamy, Chaitanya, et al.
Pubblicazione: (2025)

Towards the Characterization of Terminal Cut Functions: a Condition for Laminar Families
di: Chen, Yu, et al.
Pubblicazione: (2023)

Dichotomies for Maximum Matching Cut: $H$-Freeness, Bounded Diameter, Bounded Radius
di: Lucke, Felicia, et al.
Pubblicazione: (2023)

Density Matters: A Complexity Dichotomy of Deleting Edges to Bound Subgraph Density
di: Bentert, Matthias, et al.
Pubblicazione: (2026)

Parameterized Complexity of s-Club Cluster Edge Deletion: When Is the Diameter Bound Necessary?
di: Gaikwad, Ajinkya
Pubblicazione: (2025)

EPTAS for Hard Graph Cut Problems for Dense Graphs
di: Deguchi, Kaisei, et al.
Pubblicazione: (2026)

Random local access for sampling k-SAT solutions
di: Dong, Dingding, et al.
Pubblicazione: (2024)

Thin Trees via $k$-Respecting Cut Identities
di: Daga, Mohit
Pubblicazione: (2025)

Strong Conflict-Free Vertex-Connection via Twin Cover: Kernelization and Chromatic Bounds
di: German, Samuel
Pubblicazione: (2026)

A Dichotomy Theorem for Linear Time Homomorphism Orbit Counting in Bounded Degeneracy Graphs
di: Paul-Pena, Daniel, et al.
Pubblicazione: (2022)

An Exact Solver for Submodular Knapsack Problems
di: Münch, Sabine, et al.
Pubblicazione: (2025)

Optimal Mixing via Tensorization for Random Independent Sets on Arbitrary Trees
di: Efthymiou, Charilaos, et al.
Pubblicazione: (2023)

Near-Optimal Constructive Bounds for $\ell_2$ Prefix Discrepancy and Steinitz Problems via Affine Spectral Independence
di: Dutta, Kunal, et al.
Pubblicazione: (2026)

Maximum Biclique for Star 1,2,3 -free and Bounded Bimodularwidth Twin-free Bipartite Graphs $\star$
di: de Montgolfier, Fabien, et al.
Pubblicazione: (2025)

Finding d-Cuts in Graphs of Bounded Diameter, Graphs of Bounded Radius and H-Free Graphs
di: Lucke, Felicia, et al.
Pubblicazione: (2024)