# Homework 17

Due Monday, April 13 at 5:00 PM. Please refer to the homework policy here.

## Problems

1. Prove that $1 + x \leq e^x$ for all $x$.1
2. Suppose now that each set $S_j$ also had a nonnegative cost $c_j$. Describe how to modify the (uniform cost) set cover algorithm from class to give a $O(\ln m)$ approximation for set cover with nonnegative costs. You can refer to the lecture for the parts of the analysis that are the exact same, but you should reprove the parts that might differ.

1 Hint: Both sides are equal at $x=0$. What is the rate of change as we move away from 0?