Optimal Lower Bounds for Universal and Differentially Private Steiner Tree and TSP
Anand BhalgatDeeparnab ChakrabartySanjeev KhannaPublished in: CoRR (2010)
Keyphrases
- steiner tree
- differentially private
- lower bound
- optimal solution
- linear programming relaxation
- worst case
- np hard
- upper bound
- objective function
- differential privacy
- traveling salesman problem
- shortest path
- branch and bound algorithm
- combinatorial optimization
- linear programming
- dynamic programming
- special case
- facility location
- search space
- genetic algorithm