<p>Is there an algorithm that finds a minimum vertex cover with an approximation factor of 3/2
for a planar graph?</p>

CC BY-SA 4.0
2023-12-28T00:29:54.933Z
This seems like a HW exercise. The answer is Yes. Use LP rounding + the 4-color theorem.
user3508551
CC BY-SA 4.0
2023-12-28T06:22:00.460Z
Baker's technique can do $1+\varepsilon$ approximation for any $\varepsilon > 0$.
Laakeri
<optimization><linear-programming>
Is there an algorithm that finds a minimum vertex cover with an approximation factor of 3/2 for a planar graph?
John Stuart
# Is there an algorithm that finds a minimum vertex cover with an approximation factor of 3/2 for a planar graph?

(Asked by: username_0 on 2023-12-27)

Is there an algorithm that finds a minimum vertex cover with an approximation factor of 3/2
for a planar graph?

**Tags:** optimization, linear-programming
> **Comments:**
> **username_1**: This seems like a HW exercise. The answer is Yes. Use LP rounding + the 4-color theorem.  
> **username_2**: Baker's technique can do $1+\varepsilon$ approximation for any $\varepsilon > 0$.  

---

## 0 answers

