Dec
12
comment Minimal cumulative set sum
I would also recommend the following paper for improved bounds, special cases, and hardness results for the scheduling problem. people.idsia.ch/~monaldo/papers/MOR-schedprec-11.pdf. See also the paper on 2-\epsilon hardness under a variant of unique games by Bansal and Khot win.tue.nl/~nikhil/pubs/focs-09-version.pdf.
Dec
3
comment Modifying Hopcroft-Karp algorithm to get approximate bipartite matching
@DavidEppstein I think stopping the augmenting path algorithm after paths reach $\Omega(1/\epsilon)$ should give a $(1-\epsilon)$-approximation, no?
Nov
27
awarded Nice Answer
Nov
27
revised Books/Lecture Notes on Parametrized Complexity
added 303 characters in body
Nov
26
comment Algorithmic advantages of pathwidth over treewidth
This is again not a clean answer to the original question. The flow-cut gap in pathwidth k graphs is known to be bounded by f(k) for some function f via a result of Lee and Sidiropoulos. It is an important open problem whether such a result holds for treewidth. The case k=3 is open for treewidth.
Nov
26
comment Algorithmic advantages of pathwidth over treewidth
There are problems that are easy on paths but NP-Hard on trees. These include minimum multicut and maximum integer multiflow.
Nov
6
comment Maximizing a submodular function with restricted values
(3) implies (4). If a monotone $f$ satisfies (3) then it is essentially the rank function of a matroid $M$ (we can suppress the elements $x$ with $f(x) = 0$). Maximizing $f$ subject to a cardinality constraint is the same as finding min of $k$ and the rank of $M$ which is poly-time solvable.
Oct
30
comment Theoretical results for random forests?
@D.W Write to the authors and see if they are willing to share a copy. I am aware of the results but haven't seen the paper myself.
Oct
28
comment Theoretical results for random forests?
There is a new paper in upcoming SODA'15 that may be relevant. See meetings.siam.org/sess/dsp_talk.cfm?p=68795
Oct
25
awarded Necromancer
Aug
20
comment Maximum local edge connectivity
Chao, you are of aware of one case where the Gomory-Hu tree can be computed in close to $O(mn)$ time, namely unweighted undirected graphs. So, in principle, there is no need to compute $n$ max flows.
Jul
26
comment Theoretical study of coordinate descent methods
Sebastien Bubeck has a recent monograph on convex optimization and iteration complexity for various methods. May be a useful place to look. blogs.princeton.edu/imabandit/2014/05/16/…
Jul
24
answered Node-weighted steiner problem with few terminals
Jul
18
comment Sparse subgraph preserving rooted edge connectivity up to $k$
For Eulerian digraphs a result of Bang-Jensen, Frank and Jordan gives such a result. epubs.siam.org/doi/abs/10.1137/S0036142993226983, in fact it gives a stronger decomposition result. Similar result is known under slightly less restrictive conditions due to Gabow. For general graphs I don't the answer and am curious as well. My guess would be that the answer is negative.
Jun
27
comment Literature for Generalized Load Balancing
@SashoNikolov the question is ill phrased I think. I looked at the refs and figured it was the multidimensional/vector scheduling problem.
Jun
26
comment What is simplest polynomial algorithm for PLANARITY?
Reducing to 3-connected case is a conceptually simple and should be explained in any case. If we are not too interested in efficiency reducing to 3-connected case can be easily done. Check all 2-node cuts.
Jun
26
comment Literature for Generalized Load Balancing
@SashoNikolov The objective function is basically a makespan constraint over $k$ dimensions. This is related to vector scheduling where each job has $k$ dimensions.
Jun
26
comment Literature for Generalized Load Balancing
One can get an $O(\log k/\log \log k)$-approximation for this problem. Look at a recent Arxiv paper below and references in that paper. arxiv.org/pdf/1406.5943v1.pdf
Jun
21
awarded Enlightened
Jun
20
answered A flowchart for concentration bounds
1 2 3 4 5