exam3 toughies Flashcards
NP-Complete Reduction Steps
Reducing A->B
- Prove B is in NP
- Write Input, Output, Runtime, Correctness
LP Standard Form
Max C(x)
A(x) <= b
X >= 0
Dual Standard Form
Min b(y)
A(y) >= c
Y >= 0
How many constraints in an LP?
n non-negativity constraints + m constraints
What is the upper bound for the number of vertices in an LP?
n+m choose N
What is the upper bound for the number of neighbors in an LP?
n*m
Simplex Algorithm
- Start at x=0 and check if there is a feasible area
- Look for neighbor vertex with higher objective value and move to that vertex
- Repeat
Weak Duality + its implication
Any feasible point in the dual is an upper bound of any feasible point in the primal => if both have an optimum value, then it’s the same value
Primal and dual feasibility / unbounded relationship
If one if unbounded, the other is infeasible. If dual is infeasible, primal is either unbounded or infeasible
Strong Duality + implication
primal is feasible and bounded if and only if the dual is feasible and bounded => primal has an optimum if and only if dual has an optimum
How to convert an LP solution back to an ILP and what is the expected value?
Round each value of y using randomized rounding
If y=0.75, then round y to 1 with probability 0.75, and to 0 with probability 0.25
Expected value >= (1-1/e) m* where m* is the optimal value for the ILP
How can we use ILP/LP to get heuristics for NP-Hard problems?
Reduce NP-Hard to ILP
Relax to LP and solve
Do Randomized Rounding
=> Results in a feasible point and reasonable heuristic
3/4 approximation
Can use a combo of LP-Relaxation and Randomized Rounding method. Just perform both and pick the best value. Expected performance >= 3/4 m* where m* is the optimal solution
