Consider the statements: A. There does not exist a polynomial time algorithm…
2022
Consider the statements:
A. There does not exist a polynomial time algorithm to solve integer linear programming problem.
B. Main focus of PERT is 'minimizing time'.
Choose the correct option about the statements A and B.
- A.
A is True; B is True
- B.
A is True; B is False
- C.
A is False; B is True
- D.
A is False; B is False
Attempted by 39 students.
Show answer & explanation
Correct answer: B
Answer: The statement that there is no polynomial-time algorithm for integer linear programming is true; the statement that PERT's main focus is "minimizing time" is false.
Integer linear programming (ILP): The decision version of ILP is NP-complete and the optimization version is NP-hard. Therefore, no polynomial-time algorithm is known for the general ILP; absent a proof that P = NP, ILP is treated as not solvable in polynomial time in general.
PERT (Program Evaluation and Review Technique): PERT is used to estimate project completion times, model activity durations probabilistically, and identify the critical path for planning and control. It is not primarily an algorithm for minimizing project duration (techniques such as crashing or resource optimization address minimization).
Conclusion: The correct choice is the one that states the integer linear programming claim is true and the PERT claim is false.