Cover Image

Fast Approximation Algorithms for Euclidean Minimum Weight Perfect Matching

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Hougardy, Stefan, Tammemaa, Karolina
Format:	Preprint
Published:	2024
Subjects:	Computational Geometry Data Structures and Algorithms Combinatorics 68R10
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Unbent Collections of Orthogonal Drawings
by: Antić, Todor, et al.
Published: (2025)

A 13/6-Approximation for Strip Packing via the Bottom-Left Algorithm
by: Hougardy, Stefan, et al.
Published: (2025)

Orientability of Undirected Phylogenetic Networks to a Desired Class: Practical Algorithms and Application to Tree-Child Orientation
by: Urata, Tsuyoshi, et al.
Published: (2024)

Online Duet between Metric Embeddings and Minimum-Weight Perfect Matchings
by: Bhore, Sujoy, et al.
Published: (2023)

On algorithmic applications of sim-width and mim-width of $(H_1, H_2)$-free graphs
by: Munaro, Andrea, et al.
Published: (2022)

The Minimum Eternal Vertex Cover Problem on a Subclass of Series-Parallel Graphs
by: Calamoneri, Tiziana, et al.
Published: (2025)

On the Complexity of Distance-$d$ Independent Set Reconfiguration
by: Hoang, Duc A.
Published: (2022)

A Faster Algorithm for Independent Cut
by: Chernyshev, Vsevolod, et al.
Published: (2025)

Fast Algorithms for Minimum Homology Basis
by: Dhar, Amritendu, et al.
Published: (2021)

Improved Approximation Algorithms for the Expanding Search Problem
by: Griesbach, Svenja M., et al.
Published: (2023)

An Improved Upper Bound for the Euclidean TSP Constant Using Band Crossovers
by: Gaudio, Julia, et al.
Published: (2026)

Decline and Fall of the ICALP 2008 Modular Decomposition algorithm
by: Atherton, William, et al.
Published: (2024)

Optimal Adjacency Labels for Subgraphs of Cartesian Products
by: Esperet, Louis, et al.
Published: (2022)

Optimal Online Bipartite Matching in Degree-2 Graphs
by: Bhangale, Amey, et al.
Published: (2025)

Polynomial-Time Approximation Schemes for Independent Packing Problems on Fractionally Tree-Independence-Number-Fragile Graphs
by: Galby, Esther, et al.
Published: (2023)

Adjacency Labeling Schemes for Small Classes
by: Bonnet, Édouard, et al.
Published: (2024)

Quadratic-Time Algorithm for the Maximum-Weight $(k, \ell)$-Sparse Subgraph Problem
by: Deák, Bence, et al.
Published: (2025)

Optimized Degree Realization: Minimum Dominating Set & Maximum Matching
by: Bar-Noy, Amotz, et al.
Published: (2025)

Cops and Robbers on Multi-Layer Graphs
by: Enright, Jessica, et al.
Published: (2023)

Polynomial-size encoding of all cuts of small value in integer-valued symmetric submodular functions
by: Oum, Sang-il, et al.
Published: (2026)

Fast Static and Dynamic Approximation Algorithms for Geometric Optimization Problems: Piercing, Independent Set, Vertex Cover, and Matching
by: Bhore, Sujoy, et al.
Published: (2024)

A New Construction of the Vietoris-Rips Complex
by: Rieser, Antonio
Published: (2023)

Optimal Discretization is Fixed-parameter Tractable
by: Kratsch, Stefan, et al.
Published: (2020)

Reconfiguration of Independent Transversals
by: Buys, Pjotr, et al.
Published: (2024)

The Behavior of Tree-Width and Path-Width under Graph Operations and Graph Transformations
by: Gurski, Frank, et al.
Published: (2024)

Faster Approximation Scheme for Euclidean $k$-TSP
by: van Wijland, Ernest, et al.
Published: (2023)

Finding Spanning Trees with Perfect Matchings
by: Bérczi, Kristóf, et al.
Published: (2024)

The Bottom-Left Algorithm for the Strip Packing Problem
by: Hougardy, Stefan, et al.
Published: (2024)

Minimum-Weight Half-Plane Hitting Set
by: Liu, Gang, et al.
Published: (2025)

A Fast Algorithm for Finding Minimum Weight Cycles in Mining Cyclic Graph Topologies
by: Shakeri, Heman, et al.
Published: (2025)

Branch-width of represented matroids in matrix multiplication time
by: Choi, Mujin, et al.
Published: (2026)

Blossom VI: A Practical Minimum Weight Perfect Matching Algorithm
by: Arkhipov, Pavel, et al.
Published: (2026)

m-Eternal Domination and Variants on Some Classes of Finite and Infinite Graphs
by: Calamoneri, Tiziana, et al.
Published: (2025)

Euclidean Affine Functions and Applications to Calendar Algorithms
by: Neri, Cassio, et al.
Published: (2021)

On Sparse Covers of Minor Free Graphs, Low Dimensional Metric Embeddings, and other applications
by: Filtser, Arnold
Published: (2024)

A Dichotomy for 1-Planarity with Restricted Crossing Types Parameterized by Treewidth
by: Cabello, Sergio, et al.
Published: (2025)

On Computing Vertex Connectivity of 1-Plane Graphs
by: Biedl, Therese, et al.
Published: (2022)

Zone Theorem for Arrangements in three dimensions
by: Saxena, Sanjeev
Published: (2020)

On the twin-width of near-regular graphs
by: Heinrich, Irene, et al.
Published: (2025)

Interval Graphs are Reconstructible
by: Heinrich, Irene, et al.
Published: (2025)