`On Mon, 2011-11-14 at 18:39 +0100, Stephane Eranian wrote:> On Mon, Nov 14, 2011 at 5:00 PM, Peter Zijlstra <peterz@infradead.org> wrote:> > On Mon, 2011-11-14 at 15:26 +0100, Stephane Eranian wrote:> >> There is an edge from the source to all the events.> >> There is an edge from all the counters to the sync.> >> There is an edge between an event and a counter, if> >> it can count the event.> >>> >> The capacity of any edge is 1.> >> > Ah indeed.> >> > So that gives:> >> >  E = e+e*c+c ~= O(c^2); since e<=c> >  V = 2+e+c   ~= O(c)> >> > Then going by:> >> > http://en.wikipedia.org/wiki/Maximum_flow_problem> >> > we have to stay away from Edmonds-Karp.> >> > Ford-Fulkerson would end up being O(E * c) = O(c^3), since max |f| is c.> > Which is pretty much identical to all these O(V^2 E) = O(c^3) as well.> >> > Dinitz blocking flow with dynamic trees looks more interesting at O(c^2> > log(c)). Push relabel with dynamic trees looks to be best at O(c^2),> > since V^2/E ends up being c^2/c^2 = 1.> >> > Creating the graph itself will be O(c^2) as well, due to E.> >> I think we are in the special case of a bi-partite graph with unit capacities,> thus the complexity can be reduced even more.> > See Special Cases in http://en.wikipedia.org/wiki/Dinic%27s_algorithmYeah, I found that, but that still reduces to O(c^2.5) which is over theO(c^2) of Push relabel with dynamic trees.I haven't managed to wrap my head around this stuff well enough to evenstart to have an idea if this constraint (bi-partite and unitcapacities) will have any considerable effect on the other algorithms.Also, we don't need an exhaustive max flow solution, any flow that'shigh enough to fit the required capacity will do, this too couldpossibly be used to lower the (average) complexity bound.I would really really like it to not average to O(n^3), that's justsilly expensive.Also, do you have any objections to me merging Roberts stuff (providedit passes review etc.) while you poke at alternative solutions? We canalways replace the stuff again if we find anything that works better.`