Changes between Version 40 and Version 41 of Check


Ignore:
Timestamp:
Oct 24, 2010, 11:00:03 PM (14 years ago)
Author:
olorin
Comment:

--

Legend:

Unmodified
Added
Removed
Modified

  • Check

    v40 v41  
    297297
    298298[[Image(Percentage_task-scheduling.png)]]
    299 Figure 1. Percentage of addition to the optimal of the approximation solution - Twice the optimal is represented by 100%.
     299
     300Percentage of addition to the optimal of the approximation solution - Twice the optimal is represented by 100%.
    300301
    301302[[Image(Runtime_task-scheduling.png)]]
    302 Figure 2. Runtime comparisons (on semi-logarithmic scale) of variants of the approximation solution, GH is the standard Gomory-Hu algorithm, AGH is our solution of the scheduling problem based on Gomory-Hu.
     303
     304Runtime comparisons (on semi-logarithmic scale) of variants of the approximation solution, GH is the standard Gomory-Hu algorithm, AGH is our solution of the scheduling problem based on Gomory-Hu.
    303305
    304306The approximation solution to the scheduling problem also proves to be a viable alternative from the complexity point of view. Asymptotically it has the same complexity as the Gomory-Hu algorithm it is based on, although with a higher constant.