Before revision:  To complement our algorithmic contributions, we provide a hardness result which states that no algorithm making polynomially many queries to the value and independence oracles can achieve an approximation better than k + 1/2 + \varepsilon  .
After revision:  To complement our algorithmic contributions, we provide a hardness result which states that no algorithm making polynomially many oracle queries can achieve an approximation better than k + 1/2 + \varepsilon .