Two Approaches to Approximation Algorithms for Vertex Deletion Problems

Description

We give a 2-approximation algorithm for Cluster Vertex Deletion. This tight result matches the hardness lower bound. We obtain a new deterministic 7/3-approximation algorithm for Feedback Vertex Set in Tournaments. This result is based on the LP given by just one round of Sherali-Adams. We find a new, simpler deterministic (2 + epsilon)-approximation algorithm for Split Vertex Deletion. We give a 2-approximation algorithm for Claw-Free Vertex Deletion in triangle-free graphs. In the case of general graphs we prove that it is UGC-hard to obtain an approximation ratio lower than 3. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

Links & Downloads

1. https://dipot.ulb.ac.be/dspace/bitstream/2013/333891/3/table_of_contents.pdf
2. https://dipot.ulb.ac.be/dspace/bitstream/2013/333891/5/ContratDiDrescher.pdf
3. https://dipot.ulb.ac.be/dspace/bitstream/2013/333891/4/cover_thesis_matthew_drescher.pdf
4. http://hdl.handle.net/2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/333891

Tags

Mathématiques

approximation, algorithms

Additional Fields

Identifer	oai:union.ndltd.org:ulb.ac.be/oai:dipot.ulb.ac.be:2013/333891
Date	15 November 2021
Creators	Drescher, Matthew
Contributors	Fiorini, Samuel, Cardinal, Jean, Joret, Gwenaël
Publisher	Universite Libre de Bruxelles, Université libre de Bruxelles, Faculté des Sciences – Mathématiques, Bruxelles
Source Sets	Université libre de Bruxelles
Language	English
Detected Language	English
Type	info:eu-repo/semantics/doctoralThesis, info:ulb-repo/semantics/doctoralThesis, info:ulb-repo/semantics/openurl/vlink-dissertation
Format	3 full-text file(s): application/pdf | application/pdf | application/pdf
Rights	3 full-text file(s): info:eu-repo/semantics/openAccess | info:eu-repo/semantics/closedAccess | info:eu-repo/semantics/restrictedAccess