Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Publication

A Simple LP-Based Approximation Algorithm for the Matching Augmentation Problem

Ola Nils Anders Svensson, Etienne Michel François Bamas, Marina Rebekah Rosie Drygala
2022
Conference Papers

Résumé

The Matching Augmentation Problem (MAP) has recently received significant attention as an important step towards better approximation algorithms for finding cheap 2-edge connected subgraphs. This has culminated in a 5/3-approximation algorithm. However, the algorithm and its analysis are fairly involved and do not compare against the problem's well-known LP relaxation called the cut LP.

Source officielle

https://infoscience.epfl.ch/entities/publication/57e1b54b-db9b-42d4-8687-eab9ea0212af

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

A Simple LP-Based Approximation Algorithm for the Matching Augmentation Problem

Graph Chatbot

Advancing Distributed AC Optimal Power Flow for Integrated Transmission-Distribution Systems

Community detection for directed networks revisited using bimodularity

Global Group Fairness in Federated Learning via Function Tracking