doc/images/bipartite_matching.eps
author Peter Kovacs <kpeter@inf.elte.hu>
Tue, 15 Mar 2011 19:32:21 +0100
changeset 936 ddd3c0d3d9bf
permissions -rw-r--r--
Implement the scaling Price Refinement heuristic in CostScaling (#417)
instead of Early Termination.

These two heuristics are similar, but the newer one is faster
and not only makes it possible to skip some epsilon phases, but
it can improve the performance of the other phases, as well.
     1 %!PS-Adobe-3.0 EPSF-3.0
     2 %%BoundingBox: 15 18 829 570
     3 %%HiResBoundingBox: 15.1913 18.4493 828.078 569.438
     4 %%Creator: Karbon14 EPS Exportfilter 0.5
     5 %%CreationDate: (04/15/06 15:20:26)
     6 %%For: (Balazs Dezso) ()
     7 %%Title: ()
     8 
     9 /N {newpath} def
    10 /C {closepath} def
    11 /m {moveto} def
    12 /c {curveto} def
    13 /l {lineto} def
    14 /s {stroke} def
    15 /f {fill} def
    16 /w {setlinewidth} def
    17 /d {setdash} def
    18 /r {setrgbcolor} def
    19 /S {gsave} def
    20 /R {grestore} def
    21 
    22 N
    23 251.402 32.047 m
    24 532.945 293.946 814.484 555.844 814.484 555.844 c
    25 [] 0 d 1 0 0 r 3.92814 w s
    26 
    27 N
    28 749.012 32.047 m
    29 742.465 293.946 735.918 555.844 735.918 555.844 c
    30 [] 0 d 0 0 0 r 1.96407 w s
    31 
    32 N
    33 539.492 32.047 m
    34 637.703 293.946 735.918 555.844 735.918 555.844 c
    35 [] 0 d 0 0 0 r 1.96407 w s
    36 
    37 N
    38 172.832 32.047 m
    39 454.375 293.946 735.918 555.844 735.918 555.844 c
    40 [] 0 d 0 0 0 r 1.96407 w s
    41 
    42 N
    43 107.355 32.047 m
    44 421.637 293.946 735.918 555.844 735.918 555.844 c
    45 [] 0 d 1 0 0 r 3.92814 w s
    46 
    47 N
    48 644.25 555.844 m
    49 696.633 293.946 749.012 32.047 749.012 32.047 c
    50 [] 0 d 0 0 0 r 1.96407 w s
    51 
    52 N
    53 474.016 555.844 m
    54 611.516 293.946 749.012 32.047 749.012 32.047 c
    55 [] 0 d 1 0 0 r 3.92814 w s
    56 
    57 N
    58 683.535 32.047 m
    59 663.894 293.946 644.25 555.844 644.25 555.844 c
    60 [] 0 d 0 0 0 r 1.96407 w s
    61 
    62 N
    63 120.453 555.844 m
    64 401.992 293.946 683.535 32.047 683.535 32.047 c
    65 [] 0 d 0 0 0 r 1.96407 w s
    66 
    67 N
    68 28.7853 555.844 m
    69 356.16 293.946 683.535 32.047 683.535 32.047 c
    70 [] 0 d 1 0 0 r 3.92814 w s
    71 
    72 N
    73 539.492 32.047 m
    74 546.039 293.946 552.586 555.844 552.586 555.844 c
    75 [] 0 d 1 0 0 r 3.92814 w s
    76 
    77 N
    78 316.875 32.047 m
    79 349.613 293.946 382.351 555.844 382.351 555.844 c
    80 [] 0 d 1 0 0 r 3.92814 w s
    81 
    82 N
    83 107.355 32.047 m
    84 244.855 293.946 382.351 555.844 382.351 555.844 c
    85 [] 0 d 0 0 0 r 1.96407 w s
    86 
    87 N
    88 290.687 555.844 m
    89 375.805 293.946 460.922 32.047 460.922 32.047 c
    90 [] 0 d 1 0 0 r 3.92814 w s
    91 
    92 N
    93 120.453 555.844 m
    94 290.687 293.946 460.922 32.047 460.922 32.047 c
    95 [] 0 d 0 0 0 r 1.96407 w s
    96 
    97 N
    98 172.832 32.047 m
    99 146.64 293.946 120.453 555.844 120.453 555.844 c
   100 [] 0 d 1 0 0 r 3.92814 w s
   101 
   102 N
   103 15.6913 555.844 m
   104 15.6913 555.844 l
   105 15.6913 548.614 21.5553 542.75 28.7853 542.75 c
   106 36.0163 542.75 41.8833 548.614 41.8833 555.844 c
   107 41.8833 563.075 36.0163 568.938 28.7853 568.938 c
   108 21.5553 568.938 15.6913 563.075 15.6913 555.844 c
   109 15.6913 555.844 l
   110 C
   111 S 0 0 0 r f R
   112 
   113 N
   114 16.8833 555.844 m
   115 16.8833 555.844 l
   116 16.8833 549.27 22.2113 543.942 28.7853 543.942 c
   117 35.3593 543.942 40.6913 549.27 40.6913 555.844 c
   118 40.6913 562.418 35.3593 567.747 28.7853 567.747 c
   119 22.2113 567.747 16.8833 562.418 16.8833 555.844 c
   120 16.8833 555.844 l
   121 C
   122 S 1 0.5 1 r f R
   123 
   124 N
   125 107.355 555.844 m
   126 107.355 555.844 l
   127 107.355 548.614 113.223 542.75 120.453 542.75 c
   128 127.683 542.75 133.547 548.614 133.547 555.844 c
   129 133.547 563.075 127.683 568.938 120.453 568.938 c
   130 113.223 568.938 107.355 563.075 107.355 555.844 c
   131 107.355 555.844 l
   132 C
   133 S 0 0 0 r f R
   134 
   135 N
   136 108.547 555.844 m
   137 108.547 555.844 l
   138 108.547 549.27 113.879 543.942 120.453 543.942 c
   139 127.027 543.942 132.355 549.27 132.355 555.844 c
   140 132.355 562.418 127.027 567.747 120.453 567.747 c
   141 113.879 567.747 108.547 562.418 108.547 555.844 c
   142 108.547 555.844 l
   143 C
   144 S 1 0 1 r f R
   145 
   146 N
   147 199.019 555.844 m
   148 199.019 555.844 l
   149 199.019 548.614 204.887 542.75 212.117 542.75 c
   150 219.348 542.75 225.211 548.614 225.211 555.844 c
   151 225.211 563.075 219.348 568.938 212.117 568.938 c
   152 204.887 568.938 199.019 563.075 199.019 555.844 c
   153 199.019 555.844 l
   154 C
   155 S 0 0 0 r f R
   156 
   157 N
   158 200.211 555.844 m
   159 200.211 555.844 l
   160 200.211 549.27 205.543 543.942 212.117 543.942 c
   161 218.691 543.942 224.019 549.27 224.019 555.844 c
   162 224.019 562.418 218.691 567.747 212.117 567.747 c
   163 205.543 567.747 200.211 562.418 200.211 555.844 c
   164 200.211 555.844 l
   165 C
   166 S 1 0.5 1 r f R
   167 
   168 N
   169 277.59 555.844 m
   170 277.59 555.844 l
   171 277.59 548.614 283.457 542.75 290.687 542.75 c
   172 297.918 542.75 303.781 548.614 303.781 555.844 c
   173 303.781 563.075 297.918 568.938 290.687 568.938 c
   174 283.457 568.938 277.59 563.075 277.59 555.844 c
   175 277.59 555.844 l
   176 C
   177 S 0 0 0 r f R
   178 
   179 N
   180 278.781 555.844 m
   181 278.781 555.844 l
   182 278.781 549.27 284.113 543.942 290.687 543.942 c
   183 297.262 543.942 302.59 549.27 302.59 555.844 c
   184 302.59 562.418 297.262 567.747 290.687 567.747 c
   185 284.113 567.747 278.781 562.418 278.781 555.844 c
   186 278.781 555.844 l
   187 C
   188 S 1 0 1 r f R
   189 
   190 N
   191 369.258 555.844 m
   192 369.258 555.844 l
   193 369.258 548.614 375.121 542.75 382.351 542.75 c
   194 389.582 542.75 395.445 548.614 395.445 555.844 c
   195 395.445 563.075 389.582 568.938 382.351 568.938 c
   196 375.121 568.938 369.258 563.075 369.258 555.844 c
   197 369.258 555.844 l
   198 C
   199 S 0 0 0 r f R
   200 
   201 N
   202 370.445 555.844 m
   203 370.445 555.844 l
   204 370.445 549.27 375.777 543.942 382.351 543.942 c
   205 388.926 543.942 394.258 549.27 394.258 555.844 c
   206 394.258 562.418 388.926 567.747 382.351 567.747 c
   207 375.777 567.747 370.445 562.418 370.445 555.844 c
   208 370.445 555.844 l
   209 C
   210 S 1 0 1 r f R
   211 
   212 N
   213 460.922 555.844 m
   214 460.922 555.844 l
   215 460.922 548.614 466.785 542.75 474.016 542.75 c
   216 481.246 542.75 487.109 548.614 487.109 555.844 c
   217 487.109 563.075 481.246 568.938 474.016 568.938 c
   218 466.785 568.938 460.922 563.075 460.922 555.844 c
   219 460.922 555.844 l
   220 C
   221 S 0 0 0 r f R
   222 
   223 N
   224 462.113 555.844 m
   225 462.113 555.844 l
   226 462.113 549.27 467.441 543.942 474.016 543.942 c
   227 480.59 543.942 485.922 549.27 485.922 555.844 c
   228 485.922 562.418 480.59 567.747 474.016 567.747 c
   229 467.441 567.747 462.113 562.418 462.113 555.844 c
   230 462.113 555.844 l
   231 C
   232 S 1 0.5 1 r f R
   233 
   234 N
   235 539.492 555.844 m
   236 539.492 555.844 l
   237 539.492 548.614 545.355 542.75 552.586 542.75 c
   238 559.816 542.75 565.68 548.614 565.68 555.844 c
   239 565.68 563.075 559.816 568.938 552.586 568.938 c
   240 545.355 568.938 539.492 563.075 539.492 555.844 c
   241 539.492 555.844 l
   242 C
   243 S 0 0 0 r f R
   244 
   245 N
   246 540.683 555.844 m
   247 540.683 555.844 l
   248 540.683 549.27 546.012 543.942 552.586 543.942 c
   249 559.16 543.942 564.492 549.27 564.492 555.844 c
   250 564.492 562.418 559.16 567.747 552.586 567.747 c
   251 546.012 567.747 540.683 562.418 540.683 555.844 c
   252 540.683 555.844 l
   253 C
   254 S 1 0 1 r f R
   255 
   256 N
   257 631.156 555.844 m
   258 631.156 555.844 l
   259 631.156 548.614 637.019 542.75 644.25 542.75 c
   260 651.48 542.75 657.348 548.614 657.348 555.844 c
   261 657.348 563.075 651.48 568.938 644.25 568.938 c
   262 637.019 568.938 631.156 563.075 631.156 555.844 c
   263 631.156 555.844 l
   264 C
   265 S 0 0 0 r f R
   266 
   267 N
   268 632.348 555.844 m
   269 632.348 555.844 l
   270 632.348 549.27 637.676 543.942 644.25 543.942 c
   271 650.824 543.942 656.156 549.27 656.156 555.844 c
   272 656.156 562.418 650.824 567.747 644.25 567.747 c
   273 637.676 567.747 632.348 562.418 632.348 555.844 c
   274 632.348 555.844 l
   275 C
   276 S 1 0.5 1 r f R
   277 
   278 N
   279 722.82 555.844 m
   280 722.82 555.844 l
   281 722.82 548.614 728.687 542.75 735.918 542.75 c
   282 743.149 542.75 749.012 548.614 749.012 555.844 c
   283 749.012 563.075 743.149 568.938 735.918 568.938 c
   284 728.687 568.938 722.82 563.075 722.82 555.844 c
   285 722.82 555.844 l
   286 C
   287 S 0 0 0 r f R
   288 
   289 N
   290 724.012 555.844 m
   291 724.012 555.844 l
   292 724.012 549.27 729.344 543.942 735.918 543.942 c
   293 742.492 543.942 747.82 549.27 747.82 555.844 c
   294 747.82 562.418 742.492 567.747 735.918 567.747 c
   295 729.344 567.747 724.012 562.418 724.012 555.844 c
   296 724.012 555.844 l
   297 C
   298 S 1 0 1 r f R
   299 
   300 N
   301 801.391 555.844 m
   302 801.391 555.844 l
   303 801.391 548.614 807.254 542.75 814.484 542.75 c
   304 821.715 542.75 827.578 548.614 827.578 555.844 c
   305 827.578 563.075 821.715 568.938 814.484 568.938 c
   306 807.254 568.938 801.391 563.075 801.391 555.844 c
   307 801.391 555.844 l
   308 C
   309 S 0 0 0 r f R
   310 
   311 N
   312 802.582 555.844 m
   313 802.582 555.844 l
   314 802.582 549.27 807.91 543.942 814.484 543.942 c
   315 821.059 543.942 826.387 549.27 826.387 555.844 c
   316 826.387 562.418 821.059 567.747 814.484 567.747 c
   317 807.91 567.747 802.582 562.418 802.582 555.844 c
   318 802.582 555.844 l
   319 C
   320 S 1 0 1 r f R
   321 
   322 N
   323 15.6913 32.047 m
   324 15.6913 32.047 l
   325 15.6913 24.8165 21.5553 18.9493 28.7853 18.9493 c
   326 36.0163 18.9493 41.8833 24.8165 41.8833 32.047 c
   327 41.8833 39.2775 36.0163 45.1407 28.7853 45.1407 c
   328 21.5553 45.1407 15.6913 39.2775 15.6913 32.047 c
   329 15.6913 32.047 l
   330 C
   331 S 0 0 0 r f R
   332 
   333 N
   334 16.8833 32.047 m
   335 16.8833 32.047 l
   336 16.8833 25.4728 22.2113 20.1407 28.7853 20.1407 c
   337 35.3593 20.1407 40.6913 25.4728 40.6913 32.047 c
   338 40.6913 38.6212 35.3593 43.9493 28.7853 43.9493 c
   339 22.2113 43.9493 16.8833 38.6212 16.8833 32.047 c
   340 16.8833 32.047 l
   341 C
   342 S 0.5 0.5 1 r f R
   343 
   344 N
   345 94.2623 32.047 m
   346 94.2623 32.047 l
   347 94.2623 24.8165 100.125 18.9493 107.355 18.9493 c
   348 114.586 18.9493 120.453 24.8165 120.453 32.047 c
   349 120.453 39.2775 114.586 45.1407 107.355 45.1407 c
   350 100.125 45.1407 94.2623 39.2775 94.2623 32.047 c
   351 94.2623 32.047 l
   352 C
   353 S 0 0 0 r f R
   354 
   355 N
   356 95.4533 32.047 m
   357 95.4533 32.047 l
   358 95.4533 25.4728 100.781 20.1407 107.355 20.1407 c
   359 113.93 20.1407 119.262 25.4728 119.262 32.047 c
   360 119.262 38.6212 113.93 43.9493 107.355 43.9493 c
   361 100.781 43.9493 95.4533 38.6212 95.4533 32.047 c
   362 95.4533 32.047 l
   363 C
   364 S 0.5 0.5 1 r f R
   365 
   366 N
   367 159.734 32.047 m
   368 159.734 32.047 l
   369 159.734 24.8165 165.601 18.9493 172.832 18.9493 c
   370 180.062 18.9493 185.926 24.8165 185.926 32.047 c
   371 185.926 39.2775 180.062 45.1407 172.832 45.1407 c
   372 165.601 45.1407 159.734 39.2775 159.734 32.047 c
   373 159.734 32.047 l
   374 C
   375 S 0 0 0 r f R
   376 
   377 N
   378 160.926 32.047 m
   379 160.926 32.047 l
   380 160.926 25.4728 166.258 20.1407 172.832 20.1407 c
   381 179.406 20.1407 184.734 25.4728 184.734 32.047 c
   382 184.734 38.6212 179.406 43.9493 172.832 43.9493 c
   383 166.258 43.9493 160.926 38.6212 160.926 32.047 c
   384 160.926 32.047 l
   385 C
   386 S 0.5 0.5 1 r f R
   387 
   388 N
   389 238.305 32.047 m
   390 238.305 32.047 l
   391 238.305 24.8165 244.172 18.9493 251.402 18.9493 c
   392 258.633 18.9493 264.496 24.8165 264.496 32.047 c
   393 264.496 39.2775 258.633 45.1407 251.402 45.1407 c
   394 244.172 45.1407 238.305 39.2775 238.305 32.047 c
   395 238.305 32.047 l
   396 C
   397 S 0 0 0 r f R
   398 
   399 N
   400 239.496 32.047 m
   401 239.496 32.047 l
   402 239.496 25.4728 244.828 20.1407 251.402 20.1407 c
   403 257.976 20.1407 263.305 25.4728 263.305 32.047 c
   404 263.305 38.6212 257.976 43.9493 251.402 43.9493 c
   405 244.828 43.9493 239.496 38.6212 239.496 32.047 c
   406 239.496 32.047 l
   407 C
   408 S 0.5 0.5 1 r f R
   409 
   410 N
   411 303.781 32.047 m
   412 303.781 32.047 l
   413 303.781 24.8165 309.644 18.9493 316.875 18.9493 c
   414 324.105 18.9493 329.973 24.8165 329.973 32.047 c
   415 329.973 39.2775 324.105 45.1407 316.875 45.1407 c
   416 309.644 45.1407 303.781 39.2775 303.781 32.047 c
   417 303.781 32.047 l
   418 C
   419 S 0 0 0 r f R
   420 
   421 N
   422 304.973 32.047 m
   423 304.973 32.047 l
   424 304.973 25.4728 310.301 20.1407 316.875 20.1407 c
   425 323.449 20.1407 328.781 25.4728 328.781 32.047 c
   426 328.781 38.6212 323.449 43.9493 316.875 43.9493 c
   427 310.301 43.9493 304.973 38.6212 304.973 32.047 c
   428 304.973 32.047 l
   429 C
   430 S 0.5 0.5 1 r f R
   431 
   432 N
   433 382.351 32.047 m
   434 382.351 32.047 l
   435 382.351 24.8165 388.215 18.9493 395.445 18.9493 c
   436 402.676 18.9493 408.543 24.8165 408.543 32.047 c
   437 408.543 39.2775 402.676 45.1407 395.445 45.1407 c
   438 388.215 45.1407 382.351 39.2775 382.351 32.047 c
   439 382.351 32.047 l
   440 C
   441 S 0 0 0 r f R
   442 
   443 N
   444 383.543 32.047 m
   445 383.543 32.047 l
   446 383.543 25.4728 388.871 20.1407 395.445 20.1407 c
   447 402.019 20.1407 407.351 25.4728 407.351 32.047 c
   448 407.351 38.6212 402.019 43.9493 395.445 43.9493 c
   449 388.871 43.9493 383.543 38.6212 383.543 32.047 c
   450 383.543 32.047 l
   451 C
   452 S 0.5 0.5 1 r f R
   453 
   454 N
   455 447.828 32.047 m
   456 447.828 32.047 l
   457 447.828 24.8165 453.691 18.9493 460.922 18.9493 c
   458 468.152 18.9493 474.016 24.8165 474.016 32.047 c
   459 474.016 39.2775 468.152 45.1407 460.922 45.1407 c
   460 453.691 45.1407 447.828 39.2775 447.828 32.047 c
   461 447.828 32.047 l
   462 C
   463 S 0 0 0 r f R
   464 
   465 N
   466 449.016 32.047 m
   467 449.016 32.047 l
   468 449.016 25.4728 454.348 20.1407 460.922 20.1407 c
   469 467.496 20.1407 472.824 25.4728 472.824 32.047 c
   470 472.824 38.6212 467.496 43.9493 460.922 43.9493 c
   471 454.348 43.9493 449.016 38.6212 449.016 32.047 c
   472 449.016 32.047 l
   473 C
   474 S 0.5 0.5 1 r f R
   475 
   476 N
   477 526.394 32.047 m
   478 526.394 32.047 l
   479 526.394 24.8165 532.262 18.9493 539.492 18.9493 c
   480 546.723 18.9493 552.586 24.8165 552.586 32.047 c
   481 552.586 39.2775 546.723 45.1407 539.492 45.1407 c
   482 532.262 45.1407 526.394 39.2775 526.394 32.047 c
   483 526.394 32.047 l
   484 C
   485 S 0 0 0 r f R
   486 
   487 N
   488 527.586 32.047 m
   489 527.586 32.047 l
   490 527.586 25.4728 532.918 20.1407 539.492 20.1407 c
   491 546.066 20.1407 551.394 25.4728 551.394 32.047 c
   492 551.394 38.6212 546.066 43.9493 539.492 43.9493 c
   493 532.918 43.9493 527.586 38.6212 527.586 32.047 c
   494 527.586 32.047 l
   495 C
   496 S 0.5 0.5 1 r f R
   497 
   498 N
   499 591.871 32.047 m
   500 591.871 32.047 l
   501 591.871 24.8165 597.734 18.9493 604.965 18.9493 c
   502 612.195 18.9493 618.062 24.8165 618.062 32.047 c
   503 618.062 39.2775 612.195 45.1407 604.965 45.1407 c
   504 597.734 45.1407 591.871 39.2775 591.871 32.047 c
   505 591.871 32.047 l
   506 C
   507 S 0 0 0 r f R
   508 
   509 N
   510 593.062 32.047 m
   511 593.062 32.047 l
   512 593.062 25.4728 598.39 20.1407 604.965 20.1407 c
   513 611.539 20.1407 616.871 25.4728 616.871 32.047 c
   514 616.871 38.6212 611.539 43.9493 604.965 43.9493 c
   515 598.39 43.9493 593.062 38.6212 593.062 32.047 c
   516 593.062 32.047 l
   517 C
   518 S 0.5 0.5 1 r f R
   519 
   520 N
   521 670.441 32.047 m
   522 670.441 32.047 l
   523 670.441 24.8165 676.305 18.9493 683.535 18.9493 c
   524 690.766 18.9493 696.633 24.8165 696.633 32.047 c
   525 696.633 39.2775 690.766 45.1407 683.535 45.1407 c
   526 676.305 45.1407 670.441 39.2775 670.441 32.047 c
   527 670.441 32.047 l
   528 C
   529 S 0 0 0 r f R
   530 
   531 N
   532 671.633 32.047 m
   533 671.633 32.047 l
   534 671.633 25.4728 676.961 20.1407 683.535 20.1407 c
   535 690.109 20.1407 695.441 25.4728 695.441 32.047 c
   536 695.441 38.6212 690.109 43.9493 683.535 43.9493 c
   537 676.961 43.9493 671.633 38.6212 671.633 32.047 c
   538 671.633 32.047 l
   539 C
   540 S 0 0 1 r f R
   541 
   542 N
   543 735.918 32.047 m
   544 735.918 32.047 l
   545 735.918 24.8165 741.781 18.9493 749.012 18.9493 c
   546 756.242 18.9493 762.106 24.8165 762.106 32.047 c
   547 762.106 39.2775 756.242 45.1407 749.012 45.1407 c
   548 741.781 45.1407 735.918 39.2775 735.918 32.047 c
   549 735.918 32.047 l
   550 C
   551 S 0 0 0 r f R
   552 
   553 N
   554 737.105 32.047 m
   555 737.105 32.047 l
   556 737.105 25.4728 742.437 20.1407 749.012 20.1407 c
   557 755.586 20.1407 760.914 25.4728 760.914 32.047 c
   558 760.914 38.6212 755.586 43.9493 749.012 43.9493 c
   559 742.437 43.9493 737.105 38.6212 737.105 32.047 c
   560 737.105 32.047 l
   561 C
   562 S 0 0 1 r f R
   563 
   564 N
   565 801.391 32.047 m
   566 801.391 32.047 l
   567 801.391 24.8165 807.254 18.9493 814.484 18.9493 c
   568 821.715 18.9493 827.578 24.8165 827.578 32.047 c
   569 827.578 39.2775 821.715 45.1407 814.484 45.1407 c
   570 807.254 45.1407 801.391 39.2775 801.391 32.047 c
   571 801.391 32.047 l
   572 C
   573 S 0 0 0 r f R
   574 
   575 N
   576 802.582 32.047 m
   577 802.582 32.047 l
   578 802.582 25.4728 807.91 20.1407 814.484 20.1407 c
   579 821.059 20.1407 826.387 25.4728 826.387 32.047 c
   580 826.387 38.6212 821.059 43.9493 814.484 43.9493 c
   581 807.91 43.9493 802.582 38.6212 802.582 32.047 c
   582 802.582 32.047 l
   583 C
   584 S 0.5 0.5 1 r f R
   585 
   586 %%EOF