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 find every feasible solution efficiently
B. To prove that every problem is easy
C. To find a near-optimal solution efficiently
D. To convert optimization into sorting

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

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

3 What does the approximation ratio describe?

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

4 What is an optimal solution to an optimization problem?

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

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

Approximation basics Easy
A. A guarantee of constant running time
B. A guaranteed bound on solution quality
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 twice the optimal value
C. A solution with one selected element
D. A solution equal to the optimal value

7 What does PTAS stand for?

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

8 In task scheduling, what is the makespan?

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

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. Maximize the number of idle machines
D. Increase every task's processing time

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

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

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 order in which tasks arrived
B. The duration of the smallest task
C. The number of machines in the system
D. The sum of task times assigned to it

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

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

14 What is the objective of the bin packing problem?

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

15 What condition must items placed in one bin satisfy?

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

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

Bin packing Easy
A. Into the fullest bin without checking capacity
B. Into the first existing bin with enough space
C. Into the last existing bin with any space
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 sorts all bins by remaining space
C. It checks every previously opened bin
D. It keeps only one current bin open

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 a random bin with free space
D. It selects the bin leaving the least space

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

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

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

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

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. Constant in for every
B. Polynomial in for each fixed
C. Linear in both and
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 always finds an exactly optimal solution
C. It is polynomial in both and
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. The algorithm selects vertices while
B. Every optimal cover contains both endpoints of each edge
C. Every selected vertex covers exactly two graph edges
D. The algorithm selects vertices while

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. At most
C. At most
D. Exactly

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. Increasing task identifier
B. Decreasing machine capacity
C. Nonincreasing processing time
D. Nondecreasing processing time

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. Exactly a -approximation
C. At most a -approximation
D. At most 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. A PTAS, but not an FPTAS or EPTAS from this bound
C. A constant-factor scheme, but not a PTAS under this bound
D. An FPTAS, because fixed gives polynomial time

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. Only an FPTAS is excluded; a -approximation may exist
C. A polynomial-time -approximation would imply
D. A polynomial-time -approximation would imply

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 largest two jobs have combined processing time at most
B. Every job has processing time strictly smaller than
C. The jobs can be greedily ordered by nonincreasing processing time
D. The jobs have a subset whose processing times sum exactly to

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. Solve a knapsack instance that maximizes the load of one bin
B. Find a maximum matching of compatible item pairs and leave unmatched items alone
C. Apply Next Fit after sorting all items in nondecreasing size order
D. Find a minimum spanning tree whose edges represent compatible item pairs

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 exactly bins are necessary
B. They give lower bound , while the exact optimum is
C. They give lower bound , and a -bin packing is feasible
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. Its absolute and asymptotic ratios are both at most
C. Its absolute ratio is at most , while its asymptotic ratio is unknown
D. It is an approximation scheme because the additive term becomes negligible
Previous MCQ
Unit 11
Next MCQ
Unit 13