Benchmarking Complexity of Dinic's With Scaling

Правка en4, от Chilli, 2019-03-19 03:39:48

In various places(1, 2, ), people have talked about "Dinic's With Scaling" having $$$O(VElog(U))$$$ complexity, where U is the max edge capacity. However, in just as many places, people have cast doubt about this complexity or worried that this algorithm ends up being slower in practice(12.

I had the same doubts. In fact, a couple months ago I benchmarked Dinic's with scaling on some hard test cases and thought that Dinic's with/without scaling performed similarly.

As it turns out, I benchmarked it again yesterday and found that Dinic's with scaling definitely has significantly better asymptotic complexity (by a factor of V).

Synthetic Benchmarking

I used the hard test case generator at 2 posted by ko_osaga here. The one posted at 1 creates a graph with only V edges and moreover, doesn't work for me... Notably, given a V, it generates a graph with V nodes and $$$O(V^2)$$$ edges.

The code I used was my own Dinic's implementation (originally from emaxx) found here. Notably, the SCALING variable toggles between Dinic's with scaling and without. It's a small change, as you can see.

I ran the two code across a variety of input sizes, averaging across 10 runs, then taking the log of input size and times, plotting them in a chart where blue is the runtime of Dinic's without scaling and orange is the runtime of Dinic's with scaling. Since the important thing to look at is the slope of the line, I normalized the lines to start at the same point.

Fitting a linear regression to the points, we see that the slope of Dinic's without scaling is 3.204, while the slope of Dinic's with scaling is 1.93, which correspond to complexities of $$$O(V^3)$$$ and $$$O(V^2)$$$ respectively.

In terms of actual runtime, here are some numbers on specific sizes.

Benchmarking on Problems

There are 3 flow problems, I benchmarked on — SPOJ FASTFLOW, (VNSPOJ FASTFLOW)[https://vn.spoj.com/problems/FFLOW/), and a Chinese LOJ Flow Problem (it's intended to solve this problem with Highest Label Preflow Push, which has $$$O(V^2\sqrt{E})$$$ complexity).

Also, to vouch for the superiority of my solution, here's some benchmarks with other :^)

SPOJ (V<=5000, E<=3e4) Mine: 0.30
Mine w/ scaling: 0.04

VNSPOJ (V<=5000, E<=3e4, harder test cases): No Scaling: TLE Scaling: 0.00

LOJ (V<=1200, E<=120000): No Scaling: 44 points Scaling: 88 points

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en13 Английский Chilli 2019-03-19 10:44:20 2 Tiny change: 'astest: 0.10 \n\n\nV' -> 'astest: 0.00 \n\n\nV'
en12 Английский Chilli 2019-03-19 10:13:29 109
en11 Английский Chilli 2019-03-19 06:34:52 2 Tiny change: 'haracters:\nMine: 11' -> 'haracters: \nMine: 11'
en10 Английский Chilli 2019-03-19 06:34:35 5
en9 Английский Chilli 2019-03-19 06:33:16 784 (published)
en8 Английский Chilli 2019-03-19 05:16:53 101
en7 Английский Chilli 2019-03-19 04:49:23 108
en6 Английский Chilli 2019-03-19 04:30:32 4 Tiny change: ' fastest: \n\n\n' -> ' fastest: 0.10\n\n\n'
en5 Английский Chilli 2019-03-19 04:17:31 540
en4 Английский Chilli 2019-03-19 03:39:48 334
en3 Английский Chilli 2019-03-18 22:14:30 1042 Tiny change: 'them in a chart.\n' -> 'them in a ![chart](https://i.imgur.com/gKqkpgd.jpg)\n\n'
en2 Английский Chilli 2019-03-18 05:07:24 1400
en1 Английский Chilli 2019-03-18 00:08:21 291 Initial revision (saved to drafts)