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.

Graph Chat

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

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

Chattez avec Graph Search

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