Cover Image

To buy or not to buy: deterministic rent-or-buy problems on node-weighted graphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Borst, Sander, Venzin, Moritz
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Stronger adversaries grow cheaper forests: online node-weighted Steiner problems
by: Borst, Sander, et al.
Published: (2024)

Improved Online Load Balancing in the Two-Norm
by: Borst, Sander, et al.
Published: (2025)

Learning-Augmented Online Covering Problems
by: Ameli, Afrouz Jabal, et al.
Published: (2025)

Beyond the Half-Approximation: Fair and Efficient Online Class Matching
by: Borst, Sander, et al.
Published: (2026)

Online Matching on $3$-Uniform Hypergraphs
by: Borst, Sander, et al.
Published: (2024)

A nearly optimal randomized algorithm for explorable heap selection
by: Borst, Sander, et al.
Published: (2022)

Approximation Algorithms for Combinatorial Optimization with Predictions
by: Antoniadis, Antonios, et al.
Published: (2024)

Improved girth approximation in weighted undirected graphs
by: Kadria, Avi, et al.
Published: (2025)

Fast online node labeling with graph subsampling
by: Huang, Yushen, et al.
Published: (2025)

The trace reconstruction problem for spider graphs
by: Sun, Alec, et al.
Published: (2022)

On computing approximate Lewis weights
by: Apers, Simon, et al.
Published: (2024)

Are there graphs whose shortest path structure requires large edge weights?
by: Bernstein, Aaron, et al.
Published: (2023)

Approximating optimization problems in graphs with locational uncertainty
by: Bougeret, Marin, et al.
Published: (2022)

Faster algorithms for packing forests in graphs and related problems
by: Arkhipov, Pavel, et al.
Published: (2024)

Finding coherent node groups in directed graphs
by: Kumpulainen, Iiro, et al.
Published: (2023)

SPARSE-PIVOT: Dynamic correlation clustering for node insertions
by: Dalirrooyfard, Mina, et al.
Published: (2025)

Binary weights spanning trees and the $k$-red spanning tree problem in linear time
by: Hochbaum, Dorit S.
Published: (2024)

A simple deterministic near-linear time approximation scheme for transshipment with arbitrary positive edge costs
by: Fox, Emily
Published: (2023)

Pre-assignment problem for unique minimum vertex cover on bounded clique-width graphs
by: An, Shinwoo, et al.
Published: (2024)

An efficient implementation for solving the all pairs minimax path problem in an undirected dense graph
by: Liu, Gangli
Published: (2024)

The problem of computing a $2$-T-connected spanning subgraph with minimum number of edges in directed graphs
by: Jaberi, Raed, et al.
Published: (2024)

Solving the all pairs shortest path problem after minor update of a large dense graph
by: Liu, Gangli
Published: (2024)

On 2-strong connectivity orientations of mixed graphs and related problems
by: Georgiadis, Loukas, et al.
Published: (2023)

Generation of weighted trees, block trees and block graphs
by: Ekim, Tınaz, et al.
Published: (2024)

Independent set reconfiguration in H-free graphs
by: Bartier, Valentin, et al.
Published: (2024)

Edge-weighted Matching in the Dark
by: Huang, Zhiyi, et al.
Published: (2025)

New weighted additive spanners
by: La, An, et al.
Published: (2024)

Spanner for the $0/1/\infty$ weighted region problem
by: Gudmundsson, Joachim, et al.
Published: (2024)

Online facility location with weights and congestion
by: Chakraborty, Arghya, et al.
Published: (2022)

Continuous optimization methods for the graph isomorphism problem
by: Klus, Stefan, et al.
Published: (2023)

Dynamic parameterized problems on unit disk graphs
by: An, Shinwoo, et al.
Published: (2024)

Stealing From the Dragon's Hoard: Online Unbounded Knapsack With Removal
by: Gehnen, Matthias, et al.
Published: (2025)

Grandchildren-weight-balanced binary search trees
by: Jugé, Vincent
Published: (2024)

Self-referential instances of the dominating set problem are irreducible
by: Zhou, Guangyan
Published: (2026)

A characterization of one-sided error testable graph properties in bounded degeneracy graphs
by: Lachish, Oded, et al.
Published: (2026)

Differentially private graph coloring
by: Xie, Michael, et al.
Published: (2026)

The Canadian Traveller Problem on outerplanar graphs
by: Beaudou, Laurent, et al.
Published: (2024)

Private graph colouring with limited defectiveness
by: Christiansen, Aleksander B. G., et al.
Published: (2024)

Practical algorithms for Hierarchical overlap graphs
by: Talera, Saumya, et al.
Published: (2024)

Approximating the Geometric Knapsack Problem in Near-Linear Time and Dynamically
by: Buchem, Moritz, et al.
Published: (2024)