Back to Subject

Unit 12: Approximation - Practice Quiz

ECAP538 60 Questions
0 Correct 0 Wrong 60 Left
0/60

1 What is the main purpose of an approximation algorithm?

Approximation basics Easy
A. To prove that every problem is easy
B. To find every feasible solution efficiently
C. To convert optimization into sorting
D. To find a near-optimal solution efficiently

2 Approximation algorithms are commonly used for which type of problem?

Approximation basics Easy
A. Arithmetic problems with fixed answers
B. Optimization problems that are computationally hard
C. Problems solvable only by counting
D. Problems having no possible solutions

3 What does the approximation ratio describe?

Approximation basics Easy
A. The quality of an approximate solution
B. The number of inputs in an instance
C. The memory occupied by the output
D. The running time of the compiler

4 What is an optimal solution to an optimization problem?

Approximation basics Easy
A. The first solution produced by an algorithm
B. Any solution found in polynomial time
C. A solution using the most resources
D. The best feasible solution for the objective

5 Which feature distinguishes an approximation algorithm from an ordinary heuristic?

Approximation basics Easy
A. A guaranteed bound on solution quality
B. A guarantee of constant running time
C. A restriction to numerical inputs
D. A requirement to examine every solution

6 What does a -approximation algorithm produce?

Approximation basics Easy
A. A solution found in one operation
B. A solution equal to the optimal value
C. A solution twice the optimal value
D. A solution with one selected element

7 What does PTAS stand for?

Approximation basics Easy
A. Predictable-Time Analysis Strategy
B. Polynomial Task Arrangement Sequence
C. Polynomial-Time Approximation Scheme
D. Parallel Task Allocation System

8 In task scheduling, what is the makespan?

Task scheduling Easy
A. The completion time of the entire schedule
B. The waiting time of the first task
C. The duration of the shortest task
D. The number of available machines

9 What is a common objective when scheduling independent tasks on identical machines?

Task scheduling Easy
A. Place every task on one machine
B. Minimize the schedule's makespan
C. Increase every task's processing time
D. Maximize the number of idle machines

10 In basic list scheduling, where is the next task assigned?

Task scheduling Easy
A. To the currently least-loaded machine
B. To a newly created machine each time
C. To every available machine at once
D. To the currently most-loaded machine

11 Two tasks take and time units. If they run simultaneously on two separate machines, what is the makespan?

Task scheduling Easy
A. time units
B. time units
C. time units
D. time units

12 What does the load of a machine represent in task scheduling?

Task scheduling Easy
A. The number of machines in the system
B. The sum of task times assigned to it
C. The order in which tasks arrived
D. The duration of the smallest task

13 How does the LPT scheduling rule order tasks before assigning them?

Task scheduling Easy
A. By earliest arrival time first
B. By longest processing time first
C. By shortest processing time first
D. By random processing time order

14 What is the objective of the bin packing problem?

Bin packing Easy
A. Maximize the size of every item
B. Place each item in a separate bin
C. Make all item sizes identical
D. Minimize the number of bins used

15 What condition must items placed in one bin satisfy?

Bin packing Easy
A. Their total size must not exceed capacity
B. Their number must match the bin capacity
C. Their sizes must all be equal
D. Their total size must equal zero

16 How does the First Fit method place a new item?

Bin packing Easy
A. Into the last existing bin with any space
B. Into the first existing bin with enough space
C. Into the fullest bin without checking capacity
D. Into a new bin regardless of free space

17 How does the Next Fit method handle bins?

Bin packing Easy
A. It places every item in two bins
B. It checks every previously opened bin
C. It keeps only one current bin open
D. It sorts all bins by remaining space

18 How does the Best Fit method choose a bin for an item?

Bin packing Easy
A. It selects the bin opened most recently
B. It selects the bin having the most space
C. It selects the bin leaving the least space
D. It selects a random bin with free space

19 A bin has capacity . Can items of sizes and be packed together?

Bin packing Easy
A. Yes, because item sizes are always ignored
B. No, because both exceed half the capacity
C. No, because their total is greater than
D. Yes, because their total is exactly

20 What does First Fit Decreasing do before applying First Fit?

Bin packing Easy
A. It removes all items smaller than one
B. It divides every item into equal parts
C. It doubles the capacity of each bin
D. It sorts items from largest to smallest

21 A minimization algorithm returns a solution of cost , while the optimal cost is . What is the approximation ratio on this instance?

Approximation basics Medium
A.
B.
C.
D.

22 A maximization algorithm guarantees a value of at least . If , what value is guaranteed?

Approximation basics Medium
A.
B.
C.
D.

23 Which running-time property is required of a polynomial-time approximation scheme (PTAS)?

Approximation basics Medium
A. Linear in both and
B. Constant in for every
C. Polynomial in for each fixed
D. Polynomial in for each fixed

24 What distinguishes an FPTAS from a PTAS?

Approximation basics Medium
A. It applies only to maximization problems
B. It is polynomial in both and
C. It always finds an exactly optimal solution
D. It has a fixed approximation ratio of

25 In the standard -approximation for Vertex Cover, both endpoints of every edge in a maximal matching are selected. Why is the factor obtained?

Approximation basics Medium
A. Every selected vertex covers exactly two graph edges
B. The algorithm selects vertices while
C. The algorithm selects vertices while
D. Every optimal cover contains both endpoints of each edge

26 A minimization algorithm produces a feasible solution of cost , and a proven lower bound on is . What approximation factor can be certified?

Approximation basics Medium
A. At least
B. Exactly
C. At most
D. At most

27 List scheduling assigns tasks in the order to three identical machines, always choosing a least-loaded machine. What is the resulting makespan?

Task scheduling Medium
A.
B.
C.
D.

28 For independent tasks on identical machines, what approximation guarantee does basic list scheduling provide for minimizing makespan?

Task scheduling Medium
A.
B.
C.
D.

29 How does Longest Processing Time first (LPT) choose the task order before applying list scheduling?

Task scheduling Medium
A. Nonincreasing processing time
B. Decreasing machine capacity
C. Nondecreasing processing time
D. Increasing task identifier

30 LPT schedules tasks with processing times on three identical machines. What makespan does it produce?

Task scheduling Medium
A.
B.
C.
D.

31 Tasks have processing times and must run on two identical machines. What is the average-load lower bound on the optimal makespan?

Task scheduling Medium
A.
B.
C.
D.

32 List scheduling processes tasks on two identical machines in the given order. If the optimal makespan is , what ratio does the produced makespan have to ?

Task scheduling Medium
A.
B.
C.
D.

33 The LPT approximation bound is . What does this bound become for three machines?

Task scheduling Medium
A.
B.
C.
D.

34 Next Fit processes items with bin capacity . How many bins does it use?

Bin packing Medium
A.
B.
C.
D.

35 First Fit processes items with bin capacity . How many bins does it use?

Bin packing Medium
A.
B.
C.
D.

36 For items of sizes and bin capacity , what lower bound follows from total item size?

Bin packing Medium
A. bins
B. bins
C. bins
D. bins

37 A bin has capacity , and the items are . What lower bound follows specifically from the items larger than half the bin capacity?

Bin packing Medium
A. At least bins
B. At least bins
C. At least bins
D. At least bins

38 Which standard worst-case guarantee is associated with the Next Fit bin-packing algorithm?

Bin packing Medium
A.
B.
C.
D.

39 Which expression is a standard upper bound for First Fit Decreasing (FFD)?

Bin packing Medium
A.
B.
C.
D.

40 Bins have capacity , and items arrive as . Next Fit uses four bins. How many bins does First Fit Decreasing use?

Bin packing Medium
A. bins
B. bins
C. bins
D. bins

41 For a minimization problem, an algorithm returns a solution of cost , while a valid lower-bound certificate gives . What is the strongest approximation guarantee justified solely by these values?

Approximation basics Hard
A. At most a -approximation
B. At most a -approximation
C. At most a -approximation
D. Exactly a -approximation

42 For a maximization problem, a feasible solution has value , and a relaxation proves . Under the convention that a -approximation satisfies , what factor is certified?

Approximation basics Hard
A. A factor of
B. A factor of
C. A factor of
D. A factor of

43 An algorithm returns a -approximation in time . How should this scheme be classified from the stated bound?

Approximation basics Hard
A. An EPTAS, because the ratio approaches one with
B. An FPTAS, because fixed gives polynomial time
C. A constant-factor scheme, but not a PTAS under this bound
D. A PTAS, but not an FPTAS or EPTAS from this bound

44 Suppose an L-reduction from minimization problem to minimization problem has constants and . If has an -approximation, which ratio follows for ?

Approximation basics Hard
A.
B.
C.
D.

45 For a minimization problem, it is NP-hard to distinguish instances with from those with , where . What consequence follows?

Approximation basics Hard
A. The gap excludes exact algorithms but no approximation factor
B. A polynomial-time -approximation would imply
C. A polynomial-time -approximation would imply
D. Only an FPTAS is excluded; a -approximation may exist

46 A minimization algorithm guarantees for every instance, and all instances satisfy . Which multiplicative guarantee follows?

Approximation basics Hard
A.
B.
C.
D.

47 For list scheduling of independent jobs on identical parallel machines, which worst-case makespan guarantee is valid?

Task scheduling Hard
A.
B.
C.
D.

48 List scheduling is run on three identical machines using the order , always assigning the next job to a least-loaded machine. Which outcome is correct?

Task scheduling Hard
A. , , ratio
B. , , ratio
C. , , ratio
D. , , ratio

49 The LPT rule sorts jobs by nonincreasing processing time and then list-schedules them. What guarantee does LPT provide on three identical machines?

Task scheduling Hard
A.
B.
C.
D.

50 LPT schedules jobs with processing times on two identical machines. Which statement describes the resulting approximation ratio?

Task scheduling Hard
A. LPT obtains while the optimum is , giving ratio
B. LPT obtains while the optimum is , giving ratio
C. LPT obtains while the optimum is , giving ratio
D. LPT obtains while the optimum is , giving ratio

51 Apply LPT to jobs on two identical machines. Which comparison with the optimum is correct?

Task scheduling Hard
A. LPT gives , while the optimum is
B. LPT gives , while the optimum is
C. LPT gives , while the optimum is
D. LPT gives , while the optimum is

52 A precedence-constrained instance on four identical machines has total work and critical-path length . Using for list scheduling, what instance-specific ratio is certified?

Task scheduling Hard
A. At most , because and
B. At most , because and
C. At most , because and
D. At most , because and

53 Positive integer job lengths sum to . For two identical machines, which condition is equivalent to the existence of a schedule with makespan at most ?

Task scheduling Hard
A. The jobs have a subset whose processing times sum exactly to
B. The jobs can be greedily ordered by nonincreasing processing time
C. Every job has processing time strictly smaller than
D. The largest two jobs have combined processing time at most

54 Next Fit processes capacity- items in the order . How many bins does it use, and what is the optimum?

Bin packing Hard
A. Next Fit uses bins; the optimum uses
B. Next Fit uses bins; the optimum uses
C. Next Fit uses bins; the optimum uses
D. Next Fit uses bins; the optimum uses

55 Which absolute worst-case bound follows from the fact that every pair of consecutive bins closed by Next Fit has combined load greater than ?

Bin packing Hard
A.
B.
C.
D.

56 Which expression is the tight classical worst-case upper bound for First Fit Decreasing on capacity- bin packing?

Bin packing Hard
A.
B.
C.
D.

57 First Fit Decreasing is applied to items . Which result demonstrates its absolute-ratio edge case?

Bin packing Hard
A. FFD uses bins and the optimum uses
B. FFD uses bins and the optimum uses
C. FFD uses bins and the optimum uses
D. FFD uses bins and the optimum uses

58 Every item in a bin-packing instance has size strictly greater than . Which polynomial-time method finds an optimal packing?

Bin packing Hard
A. Find a maximum matching of compatible item pairs and leave unmatched items alone
B. Find a minimum spanning tree whose edges represent compatible item pairs
C. Solve a knapsack instance that maximizes the load of one bin
D. Apply Next Fit after sorting all items in nondecreasing size order

59 An instance contains four items of size and five items of size . What do the volume bound and the count of items larger than establish?

Bin packing Hard
A. They give lower bound , and a -bin packing is feasible
B. They give lower bound , and exactly bins are necessary
C. They give lower bound , while the exact optimum is
D. They give lower bound , but at least bins are necessary

60 A bin-packing algorithm satisfies for every instance. What approximation conclusion follows directly?

Bin packing Hard
A. Its asymptotic ratio is at most , but an absolute ratio is not proved
B. It is an approximation scheme because the additive term becomes negligible
C. Its absolute ratio is at most , while its asymptotic ratio is unknown
D. Its absolute and asymptotic ratios are both at most
Previous MCQ
Unit 11
Next MCQ
Unit 13