Cover Image

A Decomposition Approach to the Weighted $k$-server Problem

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Ayyadevara, Nikhil, Chiplunkar, Ashish, Sharma, Amatya
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms Computational Complexity Discrete Mathematics F.2.2
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

NP-Completeness of the Combinatorial Distance Matrix Realisation Problem
by: Fairbairn, David L., et al.
Published: (2024)

Planarizing Gadgets for (k, l)-tight Graphs Do Not Exist
by: Chauhan, Archit, et al.
Published: (2026)

Arborescences and Shortest Path Trees when Colors Matter
by: Ardra, P. S., et al.
Published: (2024)

A Deterministic Bicriteria Approximation Algorithm for the Art Gallery Problem
by: Elbassioni, Khaled
Published: (2025)

Better Approximation for Weighted $k$-Matroid Intersection
by: Singer, Neta, et al.
Published: (2024)

Treewidth Inapproximability and Tight ETH Lower Bound
by: Bonnet, Édouard
Published: (2024)

Mim-Width is paraNP-complete
by: Bergougnoux, Benjamin, et al.
Published: (2025)

Answering Related Questions
by: Bonnet, Édouard
Published: (2025)

Coloring Hardness on Low Twin-Width Graphs
by: Bonnet, Édouard
Published: (2025)

Fairness in the k-Server Problem
by: Daneshvaramoli, Mohammadreza, et al.
Published: (2025)

Color-Constrained Arborescences in Edge-Colored Digraphs
by: Ardra, P. S., et al.
Published: (2025)

Highly Connected Steiner Subgraph -- Parameterized Algorithms and Applications to Hitting Set Problems
by: Eiben, Eduard, et al.
Published: (2023)

A Polynomial Kernel for Vertex Deletion to the Scattered Class of Proper Interval Graph and Trees
by: Jacob, Ashwin, et al.
Published: (2026)

Faster algorithms on linear delta-matroids
by: Koana, Tomohiro, et al.
Published: (2024)

Beyond Worst-Case Subset Sum: An Adaptive, Structure-Aware Solver with Sub-$2^{n/2}$ Enumeration
by: Salas, Jesus
Published: (2025)

Output-sensitive Complexity of Multi-Objective Integer Network Flow Problems
by: Könen, David, et al.
Published: (2023)

A polynomial-time algorithm for recognizing high-bandwidth graphs
by: Varona, Luis M. B.
Published: (2026)

Deterministic Minimum Steiner Cut in Maximum Flow Time
by: Ding, Matthew, et al.
Published: (2023)

Forward-backward Contention Resolution Schemes for Fair Rationing
by: Ma, Will, et al.
Published: (2025)

An O(log n)-Approximation Algorithm for (p,q)-Flexible Graph Connectivity via Independent Rounding
by: Ibrahimpur, Sharat, et al.
Published: (2025)

Approximation Algorithms for Capacitated Vehicle Routing Problems: A Comprehensive Survey
by: Chen, Yongyu
Published: (2023)

Computing parameters that generalize interval graphs using restricted modular partitions
by: Bonomo-Braberman, Flavia, et al.
Published: (2025)

Simple Combinatorial Construction of the $k^{o(1)}$-Lower Bound for Approximating the Parameterized $k$-Clique
by: Chen, Yijia, et al.
Published: (2023)

Online Matching and Contention Resolution for Edge Arrivals with Vanishing Probabilities
by: Ma, Will, et al.
Published: (2024)

Online Bipartite Matching in the Probe-Commit Model
by: Borodin, Allan, et al.
Published: (2023)

On (Random-order) Online Contention Resolution Schemes for the Matching Polytope of (Bipartite) Graphs
by: MacRury, Calum, et al.
Published: (2022)

Searching in trees with $k$-up-modular cost functions
by: Szyfelbein, Michał
Published: (2025)

SARRIGUREN: a polynomial-time complete algorithm for random $k$-SAT with relatively dense clauses
by: Sarriguren, Alfredo Goñi
Published: (2024)

Symmetric-Difference (Degeneracy) and Signed Tree Models
by: Bonnet, Édouard, et al.
Published: (2024)

An Algorithm for a Variation of the Shortest Common Superstring Problem
by: Gilfanov, Arthur
Published: (2024)

Why Linear Programming cannot solve large instances of NP-complete problems in polynomial time
by: Hofman, Radoslaw
Published: (2006)

Parameterized Complexity of Biclique Contraction and Balanced Biclique Contraction
by: Krithika, R., et al.
Published: (2023)

Problems in NP can Admit Double-Exponential Lower Bounds when Parameterized by Treewidth or Vertex Cover
by: Foucaud, Florent, et al.
Published: (2023)

Maximum $k$- vs. $\ell$-colourings of graphs
by: Nakajima, Tamio-Vesa, et al.
Published: (2023)

Asymptotically Optimal Inapproximability of Maxmin $k$-Cut Reconfiguration
by: Hirahara, Shuichi, et al.
Published: (2024)

Asymptotically Optimal Inapproximability of E$k$-SAT Reconfiguration
by: Hirahara, Shuichi, et al.
Published: (2025)

$O(n +f(k))$: Truly Linear FPT
by: Bumpus, Benjamin Merlin, et al.
Published: (2026)

The Parameterized Complexity of Vertex-Coloring Edge-Weighting
by: Aute, Shubhada, et al.
Published: (2026)

The complexity of strong conflict-free vertex-connection $k$-colorability
by: Hsieh, Sun-Yuan, et al.
Published: (2024)

A Piecewise Approach for the Analysis of Exact Algorithms
by: Clinch, Katie, et al.
Published: (2024)