Home Library Explore SAT

Home Library Explore SAT

Linear programming review Flashcards | StudBud

Explore/Linear programming review

Linear programming review

11 terms·StudBud Administration·48 plays

Review of linear programming concepts. Covers duality, mincut-max flow.

Flashcards11 cardsFPractice quizPHost liveL

Questions 11

Answers

1
The value of ILP and its relaxed LP need NOT be same.
False
True
2
If a problem can be written as an Integer Linear Program, then it can be solved in
Polynomial time
Can't be solved
Exponential time
Logarithmic time
3
You have to decide the project topic by
28th Sept
27th Sept
30th Sept
29th Sept
4
Markov's inequality gives a way to bound the probability of
being close to mean by some parameter
begin higher than mean by some parameter
none of the above
being away from mean by some parameter
5
Which was the most basic theorem we used to prove strong duality?
Weyl's theorem
Farkas Lemma
Hyperplane separation for 2 closed convex sets.
Weak Duality
6
Max cut = Min flow
True
False
7
Which of the following is NOT possible?
Primal unbounded, dual infeasible
Primal feasible, dual feasible
Primal bounded and feasible, dual unbounded
Primal infeasible, dual infeasible
8
Which one of the following was NOT developed by John Von Neumann
Duality theory for linear programming
Design architecture for Computers
Operator theory of quantum mechanics
Information theory
9
Who is this guy?
Dantzig
Lovasz
John Von Neumann
Random old guy
10
Complementary slackness implies optimality of the solutions with which of these conditions?
Primal feasiblity
Both
Any of the above
Dual feasiblity
11
Rounding is the step to convert
LP solution to ILP solution
Integral solution to fractional solution
None of the above
ILP solution to LP solution