exam 3 Flashcards
what does NP stand for?
nondeterministic polynomial time
What is a search problem?
a problem where we can efficiently verify solutions (in polynomial time)
What is NP?
class of all search problems
What is P?
class of all search problems that can be solved in polynomial time (subset of NP)
Knapsack search
- Just like Knapsack, but you have a minimum (goal) as well as a max (B)
- Solutions just needs to have weights <= B and values >= goal
Examples of P problems
MST, LP
NP-Complete
NP problems that cannot be solved in polynomial time
IS Problem
NP-Complete. A set of vertices S of a graph is an independent set if there are no edges connecting any two vertices in the set. Have goal for minimum
What is NP-Hard
Problems at least as hard as NP-Complete, but not necessarily in the class NP. Must reduce NP-Complete to NP-Hard
Clique
A set of vertices such that for any pair of vertices in the set, there is an edge between them. Have goal.
How to reduce IS->Clique
Reverse the graph
Vertex Cover
A set of vertices is a vertex cover if for every edge at least one vertex is in the cover. Have budget b and want |S| <= b
Property of a vertex cover
S is a vertex cover if and only if !S (all vertices not in S) is an independent set
What problems do we have for NP-Complete proof?
SAT, 3SAT, Clique, Vertex Cover, IS, Subset Sum, Knapsack
Is LP in P or NP?
It’s in P
Is ILP in P or NP?
NP-Complete
what is a Vertex Corner?
one of the vertices in the LP graph is an optimum solution
How do we know if we’ve found the optimal solution in an LP?
If a vertex is better than its neighbors, then it’s a global optimal point (assuming bounded and feasible)
How to check if there is a feasible area in an LP?
Start at x = 0 and check all remaining constraints, if none are satisfied, there is no solution
Are strict inequalities (< or >) allowed in LP?
No
Max-Flow as an LP
f(e) for every edge objective function: max(sum of all flows out of s) subject to: for every edge 0<= f <= c for every vertex v except for s,t: incoming flow == outgoing flow
LP Standard Form
Max C^T(x) such that Ax <= b and x >= 0
How to convert a min LP to a max?
multiply by -1
How many variables in an LP?
n for n-dimensional space
How many constraints in an LP?
m+n (m constraints + n non-negativity constraints)
What shape is an LP’s feasible region?
convex polyhedron
what is the Upper bound on number of vertices in an LP?
N+m choose N vertices
what is the Upper bound on number of neighbors?
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
What makes a region infeasible?
the constriants
How to check if an LP is feasible?
Check at x = 0 and check all the constraints to see if a region is feasible or not
what is an Unbounded area?
The optimal values for the objective function are arbitrarily large
What is the dual LP?
Finding the smallest upper bound for the primal LP
Dual LP general form
Min b transpose y
A transpose y >= c
Y >= 0
Weak Duality
Any feasible y for dual LP is an upper bound for the objective function of the primal LP. AKA:
○ C transpose x <= b transpose y
○ If x and y are both feasible points in the primal and dual
Weak Duality Corollary
If we find a feasible x and feasible y where c^T x == b^T y, then x and y are both optimal
- X is a max
- Y is a min
- c^T x == b^T y (this means objective function match)
rules on primal/dual feasibility and bounds
- If primal LP is unbounded, then dual LP must be infeasible (Dual LP can’t be bigger than infinity => must not be possible)
- If dual is unbounded, then the primal is infeasible (Since dual is minimizing, b^Ty will be negative infinity)
If dual is infeasible, then…?
primal is either infeasible or unbounded
How to check if LP is unbounded (using dual)?
If dual is infeasible and primal is feasible => primal is unbounded
Strong duality
If primal LP is feasible and bounded, then the dual LP is both feasible and bounded (and vice verse)
Strong Duality Corollary:
Primal has optimal x* if and only if dual has optimal y. c^T x == b^T y*
What other theorem can be proved using strong duality?
Max-Flow Min-Cut
Max-SAT
Similar to SAT, except the output is the assignment that maximizes the number of satisfiable clauses
What class is Max-SAT?
NP-Hard
Max-SAT simple solution and expected value
Randomly assign variables to T/F
Expected number of satisfiable clauses (E[W]) >= 1/2
Probability that clause is satisfied in Max-SAT simple solution
1-2^k
what class is ILP?
NP-Complete
In ILP, where is the optimal point?
Not guaranteed to be on a vertex
How to do LP Relaxation
remove requirement that variables are ints
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
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 Simplex method. Just perform both and pick the best value. Expected performance >= 3/4 m* where m* is the optimal solution
LP-Relaxation probability of Max-SAT clause evaluating to true
1-(1-1/k)^k
Subset sum
- Input = set of integers and t
- Output = subset of integers that add up to exactly t
NP-Complete
- Output = subset of integers that add up to exactly t
What is Undecidability
Computationally impossible: there is no algorithm that can solve the problem on every input, even with unlimited time and space
Example of undecidable problem
halting problem
