Copertina

A Lower Bound on the Competitive Ratio of the Permutation Algorithm for Online Facility Assignment on a Line

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autore principale:	Harada, Tsubasa
Natura:	Preprint
Pubblicazione:	2024
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

A Nearly Optimal Deterministic Algorithm for Online Transportation Problem
di: Harada, Tsubasa, et al.
Pubblicazione: (2024)

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

Greediness is not always a vice: Efficient Discovery Algorithms for Assignment Problems
di: Duvignau, Romaric, et al.
Pubblicazione: (2024)

An $Ω(n \log n)$ Randomized Lower Bound for Cutting a Cake into Proportionally Fair Pieces
di: Arndt, Stephen, et al.
Pubblicazione: (2026)

Robust Graph Isomorphism, Quadratic Assignment and VC Dimension
di: Dahan, Anatole, et al.
Pubblicazione: (2026)

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)

Spirals and Beyond: Competitive Plane Search with Multi-Speed Agents
di: Georgiou, Konstantinos, 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)

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

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)

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

Improved Space-Time Tradeoffs for Permutation Problems via Extremal Combinatorics
di: Ameli, Afrouz Jabal, et al.
Pubblicazione: (2026)

A Nonparametric Framework for Online Stochastic Matching with Correlated Arrivals
di: Aouad, Ali, 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)

The Role of Dimension in the Online Chasing Problem
di: Papazov, Hristo
Pubblicazione: (2023)

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

Revisiting Tree Isomorphism: An Algorithmic Bric-à-Brac
di: Ingels, Florian
Pubblicazione: (2023)

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

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

Online Graph Balancing and the Power of Two Choices
di: Bansal, Nikhil, et al.
Pubblicazione: (2026)

Online Graph Coloring for $k$-Colorable Graphs
di: Kawarabayashi, Ken-ichi, et al.
Pubblicazione: (2025)

Approximation Algorithms for Optimal Hopsets
di: Dinitz, Michael, et al.
Pubblicazione: (2025)

Algorithmic Aspects of Temporal Betweenness
di: Buß, Sebastian, et al.
Pubblicazione: (2020)

A Constant-Approximation Algorithm for Budgeted Sweep Coverage with Mobile Sensors
di: Liang, Wei, et al.
Pubblicazione: (2024)

A Truly Subcubic Combinatorial Algorithm for Induced 4-Cycle Detection
di: Abboud, Amir, et al.
Pubblicazione: (2025)

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

Greedy Algorithms for Shortcut Sets and Hopsets
di: Bals, Ben, et al.
Pubblicazione: (2025)

Efficient Online Sensitivity Analysis For The Injective Bottleneck Path Problem
di: Kaymakov, Kirill V., et al.
Pubblicazione: (2024)

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

An Effective Branch-and-Bound Algorithm with New Bounding Methods for the Maximum $s$-Bundle Problem
di: Xue, Jinghui, et al.
Pubblicazione: (2024)

Matching Algorithms in the Sparse Stochastic Block Model
di: Brandenberger, Anna, et al.
Pubblicazione: (2024)

An Approximation Algorithm for Monotone Submodular Cost Allocation
di: Mizutani, Ryuhei
Pubblicazione: (2025)

Minimum Sum Set Cover: Structures and Algorithm
di: Zhang, Zhongyi, et al.
Pubblicazione: (2026)

Terminal Steiner tree problem : Complexity and Algorithms
di: S, Jyothish, et al.
Pubblicazione: (2026)

Parameterized Algorithms for Balanced Cluster Edge Modification Problems
di: Madathil, Jayakrishnan, et al.
Pubblicazione: (2024)