I’m trying to figure out if there is some deterministic algorithm for this problem.
Initially I thought this would be known, but seems like it is not as trivial.
I blog about algorithm and theory related stuff…
I try to get sublime text’s markdown syntax highlighter to work with markdown + latex. (thus support even more of pandoc flavored markdown.)
Here is the current code. https://gist.github.com/Mgccl/195ce33124f384a2f4e4
I’m doing research on ways to compute maximum flow over a unit capacity undirected graph with a subset T of vertices having unit capacity in O(n2.5) time.
If T is an empty set, then there exist an algorithm to solve the problem in O(n2.5) time (in fact O(n2.375) is possible) (see the introduction in Ran Duan: Breaking the O(n2.5) Time Barrier for Undirected Unit-Capacity Maximum Flow. SODA 2013: 1171-1179 for a survey of such results)
If T is the entire set of vertices, then we can also solve it in O(n2.5) time (and this also works for directed graphs). See this paper. https://www.cs.princeton.edu/courses/archive/fall03/cs528/handouts/network%20flow%20and%20testing.pdf
but when T is just some arbitrary subset, no known algorithm takes O(n2.5) time.
Combine the techniques in 1 and 2, one can up with an algorithm that runs in O(n2.5) time if any one of the following is true
n-|T| = O(n¾).
number of edges between vertices in |T| = O(n1.5).
Each component of V\T is constant size.
I’m working on checking if one can use link/cut tree to create a generalization of finger tree.
Finger tree maintains a sequence of elements in a monoid(or one can consider a rooted path with each vertex weighted by a monoid element), and we can do many operations really fast. One can split the sequence, concat the sequence and find the sum of a sequence(so, the weight from the root to the end vertex). Note this allow us to find sum of a subsequence by split at appropriate positions and take the sum of the resulting middle sequence.
From what I read, one might want to generalize it to work on a rooted tree instead of a rooted path. We still maintain the nice property the path from the root to any vertex is unique. link/cut tree seems to do the trick as a underlying data structure. The question is more about the semantics. What would be a way to define split,concat,sum so when it is restricted to a rooted path, we get the finger tree behavior, and it’s actually useful for something else…
I guess the idea is to have this CAPTCHA during sign up or shows up once per k actions where k is relatively large?
Otherwise participation becomes a chore…
If the solution provided by the user gets stored, then one can use this to find all the interesting ways to solve the same problem.