:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Author:	Nutov, Zeev
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	https://arxiv.org/abs/2512.08350
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Tight analysis of the primal-dual method for edge-covering pliable set families
by: Nutov, Zeev
Published: (2025)

Improved approximation ratio for covering pliable set families
by: Nutov, Zeev
Published: (2024)

Improved bicriteria approximation for $k$-edge-connectivity
by: Nutov, Zeev
Published: (2025)

An $2\sqrt{k}$-approximation algorithm for minimum power $k$ edge disjoint $st$ -paths
by: Nutov, Zeev
Published: (2022)

Bicriteria approximation for $k$-edge-connectivity
by: Nutov, Zeev, et al.
Published: (2025)

Approximation and parameterized algorithms for covering disjointness-compliable set families
by: Nutov, Zeev, et al.
Published: (2025)

On $k$-connectivity oracles in $k$-connected graphs
by: Nutov, Zeev
Published: (2026)

On the cut-query complexity of approximating max-cut
by: Plevrakis, Orestis, et al.
Published: (2022)

Kernelization for list $H$-coloring for graphs with small vertex cover
by: Piecyk, Marta, et al.
Published: (2025)

Parameterized and approximation algorithms for coverings points with segments in the plane
by: Kowalska, Katarzyna, et al.
Published: (2024)

Minimum+1 Steiner Cuts and Dual Edge Sensitivity Oracle: Bridging the Gap between Global cut and (s,t)-cut
by: Bhanja, Koustav
Published: (2024)

An FPT algorithm for Matching Cut and d-cut
by: Aravind, N R, et al.
Published: (2021)

OptiRefine: Densest subgraphs and maximum cuts with $k$ refinements
by: Tu, Sijing, et al.
Published: (2025)

On the tractability and approximability of non-submodular cardinality-based $s$-$t$ cut problems in hypergraphs
by: Bengali, Vedangi, et al.
Published: (2024)

Lower bounds on the number of rounds of the quantum approximate optimization algorithm required for guaranteed approximation ratios
by: Benchasattabuse, Naphan, et al.
Published: (2023)

Shortest cover after edit
by: Mitani, Kazuki, et al.
Published: (2024)

Tight Lieb-Robinson Bound for approximation ratio in Quantum Annealing
by: Braida, Arthur, et al.
Published: (2023)

A tight quasi-polynomial bound for Global Label Min-Cut
by: Jaffke, Lars, et al.
Published: (2022)

Efficient parameterized approximation
by: Kratsch, Stefan, et al.
Published: (2025)

A simple $(2+ε)$-approximation for knapsack interdiction
by: Weninger, Noah
Published: (2026)

Nearly-tight Approximation Guarantees for the Improving Multi-Armed Bandits Problem
by: Blum, Avrim, et al.
Published: (2024)

Minimum sum vertex cover: kernelization and parameterized algorithms
by: Cao, Yixin, et al.
Published: (2024)

New approximate distance oracles and their applications
by: Kadria, Avi, et al.
Published: (2025)

Finding large sparse induced subgraphs in graphs of small (but not very small) tree-independence number
by: Lokshtanov, Daniel, et al.
Published: (2026)

A framework for boosting matching approximation: parallel, distributed, and dynamic
by: Mitrović, Slobodan, et al.
Published: (2025)

Approximately covering vertices by order-$5$ or longer paths
by: Gong, Mingyang, et al.
Published: (2024)

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

Beyond 2-approximation for k-Center in Graphs
by: Jin, Ce, et al.
Published: (2025)

FPT approximations for Capacitated Sum of Radii and Diameters
by: Filtser, Arnold, et al.
Published: (2024)

Enumerating minimal vertex covers and dominating sets with capacity and/or connectivity constraints
by: Kobayashi, Yasuaki, et al.
Published: (2023)

A $(2+\varepsilon)$-approximation algorithm for the general scheduling problem in quasipolynomial time
by: Armbruster, Alexander, et al.
Published: (2025)

List homomorphisms by deleting edges and vertices: tight complexity bounds for bounded-treewidth graphs
by: Esmer, Barış Can, et al.
Published: (2022)

Sub-$n^k$ Deterministic algorithm for minimum $k$-way cut in simple graphs
by: Daga, Mohit
Published: (2025)

A simpler and parallelizable $O(\sqrt{\log n})$-approximation algorithm for Sparsest Cut
by: Kolmogorov, Vladimir
Published: (2023)

Adaptive encodings for small and fast compressed suffix arrays
by: Díaz-Domínguez, Diego, et al.
Published: (2026)

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

Testable algorithms for approximately counting edges and triangles in sublinear time and space
by: Eden, Talya, et al.
Published: (2025)

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

A near-linear time approximation scheme for $(k,\ell)$-median clustering under discrete Fréchet distance
by: Driemel, Anne, et al.
Published: (2025)

Faster exponential algorithms for cut problems via geometric data structures
by: Kozma, László, et al.
Published: (2025)