Complexity - Easy and hard problems

4 important questions on Complexity - Easy and hard problems

Describe a hard problem

A problem for which no efficient algorithm exists to solve an arbitrary instance to optimality. (Parallel machine scheduling problem)

What are [3] ways to determine heurisitcs solution quality?

  • Compare lower and upper bounds
  • Emperical analysis
  • Worst-case analysis

What is a way to compare lower and upper bounds?

Integrality gap
  • Higher grades + faster learning
  • Never study anything twice
  • 100% sure, 100% understanding
Discover Study Smart

Give the definition of a p heuristic (use heuristic A to describe the p heuristic)

Heuristic A is a p-heuristic when it gives a solution UB(A,I) for any instance I that is no more than p times the optimal solution value OPT(I)

UB(A,I) =< p * OPT(I)

The question on the page originate from the summary of the following study material:

  • A unique study and practice tool
  • Never study anything twice again
  • Get the grades you hope for
  • 100% sure, 100% understanding
Remember faster, study better. Scientifically proven.
Trustpilot Logo