1. 2

    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.

    1. 2

      http://www.chaoxuprime.com/

      I blog about algorithm and theory related stuff…

      1. 1

        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

        1. 3

          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.

          So far.

          1. 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)

          2. 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

          1. n-|T| = O(n¾).

          2. number of edges between vertices in |T| = O(n1.5).

          3. Each component of V\T is constant size.

          1. 1

            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…

            1. 4

              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.