New answers tagged approximation-algorithms
1
Though unrelated, this lecture note contains a potential function based neat proof of the $O(\log k)$-approximation.
0
The standard pseudo-polynomial time algorithm for the partition problem with a slight change solves this problem in polynomial time.
The difference with the standard subset-sum or partition problem is the following: for the subset sum problem, to achieve a value $T$, you have to examine $T$ values of the corresponding table, however, in this case, all we ...
0
Your problem $P$: given a multiset $S = \{a_1, \dots, a_m\}$ of some $m_1$ elements equal to $a \in \mathbb{Z}^+$ and $m_2$ elements equal to $b \in \mathbb{Z}^+$, and $k \in \mathbb{N}$, what is the $k$-partition $S_1, \dots, S_k$ which maximizes $\min_i \sum_{a_j \in S_i} a_j$.
Definition A "disjoint collection" of subsets of $S$ is a collection ...
0
After a bit more searching, it appears that what I'm looking for is unlikely to exist.
In [1], it is proven that approximating the minimum maximal independence number (which is equivalent to the minimum size of an independent dominating set) within a factor of $O(n^{1-\epsilon})$ is $\mathrm{NP}$-hard for any $\epsilon > 0$. This remains true even when ...
Top 50 recent answers are included
