All Questions
2 questions
0
votes
0
answers
50
views
Can we talk about approximation when the decision problem for solution existence is NP-Hard
I am wishing to design an approximation algorithm for an optimization problem where the existence of solution for corresponding decision problem is not guaranteed. Is it wise to find an approximation ...
2
votes
1
answer
2k
views
3-Approximation Algorithm for 3-Hitting Set
I need to find a $3$-approximation algorithm for finding a $3$-hitting set.
The set-up is that I have a set $S$ and a family $\mathcal{F}$ of subsets of $S$, where each member of $\mathcal{F}$ ...
- 133