Cover Image

Approximate Minimum Tree Cover in All Symmetric Monotone Norms Simultaneously

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Kaul, Matthias, Luo, Kelin, Mnich, Matthias, Röglin, Heiko
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

Approximating Sparsest Cut in Low-Treewidth Graphs via Combinatorial Diameter
by: Chalermsook, Parinya, et al.
Published: (2021)

Connected k-Median with Disjoint and Non-disjoint Clusters
by: Eube, Jan, et al.
Published: (2025)

Effective Traveling for Metric Instances of the Traveling Thief Problem
by: Eube, Jan, et al.
Published: (2026)

Single-Machine Scheduling to Minimize the Number of Tardy Jobs with Release Dates
by: Kaul, Matthias, et al.
Published: (2024)

A $(\frac32+\frac1{\mathrm{e}})$-Approximation Algorithm for Ordered TSP
by: Armbruster, Susanne, et al.
Published: (2024)

New Algorithms and Hardness Results for Connected Clustering
by: Eube, Jan, et al.
Published: (2025)

A Survey on Graph Problems Parameterized Above and Below Guaranteed Values
by: Gutin, Gregory, et al.
Published: (2022)

Simultaneously Approximating All Norms for Massively Parallel Correlation Clustering
by: Cao, Nairen, et al.
Published: (2024)

Parameterized Algorithms for Computing Pareto Sets
by: Könen, Joshua, et al.
Published: (2025)

Exponentially faster fixed-parameter algorithms for high-multiplicity scheduling
by: Fischer, David, et al.
Published: (2022)

Parameterized Algorithms for the Drone Delivery Problem
by: Bartlmae, Simon, et al.
Published: (2026)

The Art of Being Difficult: Combining Human and AI Strengths to Find Adversarial Instances for Heuristics
by: Nikoleit, Henri, et al.
Published: (2026)

Approximation Algorithms for Connected Maximum Coverage, Minimum Connected Set Cover, and Node-Weighted Group Steiner Tree
by: D'Angelo, Gianlorenzo, et al.
Published: (2025)

Distributed Approximate Maximum Matching and Minimum Vertex Cover via Generalized Graph Decomposition
by: Davies-Peck, Peter
Published: (2026)

Supermodular Approximation of Norms and Applications
by: Kesselheim, Thomas, et al.
Published: (2024)

Dynamic $((1+ε)\ln n)$-Approximation Algorithms for Minimum Set Cover and Dominating Set
by: Solomon, Shay, et al.
Published: (2023)

Parameterized Complexity of Simultaneous Planarity
by: Fink, Simon D., et al.
Published: (2023)

New Results on a General Class of Minimum Norm Optimization Problems
by: Chen, Kuowen, et al.
Published: (2025)

A Simpler Approach for Monotone Parametric Minimum Cut: Finding the Breakpoints in Order
by: Beines, Arne, et al.
Published: (2024)

Minimizing Total Travel Time for Collaborative Package Delivery with Heterogeneous Drones
by: Erlebach, Thomas, et al.
Published: (2026)

Approximation Algorithm of Minimum All-Ones Problem for Arbitrary Graphs
by: Wang, Chen, et al.
Published: (2024)

FPT Approximation of Generalised Hypertree Width for Bounded Intersection Hypergraphs
by: Lanzinger, Matthias, et al.
Published: (2023)

Parameterized Algorithms for Minimum Sum Vertex Cover
by: Aute, Shubhada, et al.
Published: (2024)

Simultaneously Approximating All $\ell_p$-norms in Correlation Clustering
by: Davies, Sami, et al.
Published: (2023)

Additive One Approximation for Minimum Degree Spanning Tree: Breaking the $O(mn)$ Time Barrier
by: Bhattacharya, Sayan, et al.
Published: (2026)

Approximating $δ$-Covering
by: Hartmann, Tim A., et al.
Published: (2024)

Space-Efficient Parameterized Algorithms on Graphs of Low Shrubdepth
by: Bergougnoux, Benjamin, et al.
Published: (2023)

Scalable Fair Influence Blocking Maximization via Approximately Monotonic Submodular Optimization
by: Fang, Qiangpeng, et al.
Published: (2026)

A Practical 73/50 Approximation for Contiguous Monotone Moldable Job Scheduling
by: Jansen, Klaus, et al.
Published: (2026)

FPT Approximations for Fair Sum of Radii with Outliers and General Norm Objectives
by: Gadekar, Ameet
Published: (2026)

Fully Dynamic Approximate Minimum Cut in Subpolynomial Time per Operation
by: El-Hayek, Antoine, et al.
Published: (2024)

Approximation Algorithms for Clustering with Minimum Sum of Radii, Diameters, and Squared Radii
by: Friggstad, Zachary, et al.
Published: (2024)

Faster All-Pairs Minimum Cut: Bypassing Exact Max-Flow
by: Kenneth-Mordoch, Yotam, et al.
Published: (2025)

Efficient Constant-Factor Approximate Enumeration of Minimal Subsets for Monotone Properties with Weight Constraints
by: Kobayashi, Yasuaki, et al.
Published: (2020)

Tight Approximation and Kernelization Bounds for Vertex-Disjoint Shortest Paths
by: Bentert, Matthias, et al.
Published: (2024)

Exponential-Time Approximation (Schemes) for Vertex-Ordering Problems
by: Bentert, Matthias, et al.
Published: (2025)

Approximating Directed Minimum Cut and Arborescence Packing via Directed Expander Hierarchies
by: Jiang, Yonggang, et al.
Published: (2025)

A Fast Approximation Algorithm for the Minimum Balanced Vertex Separator in a Graph
by: Kolmogorov, Vladimir, et al.
Published: (2026)

Covering Approximate Shortest Paths with DAGs
by: Assadi, Sepehr, et al.
Published: (2025)

An Approximation Algorithm for Monotone Submodular Cost Allocation
by: Mizutani, Ryuhei
Published: (2025)