Sep
22
awarded Necromancer
Sep
7
awarded Nice Answer
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
Jun
15
answered Intuitively, why is the complementary slackness condition true?
Jun
15
comment Why is complementary slackness important?
I don't "get" the question. Just because we use calculators and computers to add and multiply numbers do we still need to know properties of numbers?
May
31
awarded Teacher
May
30
answered Mathematics Courses for Computer Scientists
May
3
comment Bound on a graph diameter, considering the minimal vertex degree
One can show directed graphs that have diameter $\Omega(n)$ and $\delta^-$ and $\delta^+$ are both $\Omega(n)$. For undirected graphs one can show that the diameter is $O(n/\delta)$. These are fairly simple exercises.
Apr
28
comment Is there an analogy of a vertex separator for hypergraphs?
It is common reduce edge-cuts/separators in a hypergraph $G=(V,\mathcal{E})$ to vertex cuts/separators by representing $G$ as a bipartite graph with $V$ one side and $\mathcal{E}$ on the other side. This allows vertex-separator based algorithms to be translated into edge-separator algorithms in hypergraphs. @vzn's reference in his answer is one such example and there are other such papers. I have not seen vertex separators in hyper-graphs. It is not clear that whether there is a useful and suitable definition.
Apr
24
awarded Custodian
Apr
24
reviewed Approve suggested edit on Does $\delta^+(G)+\delta^-(G) \geq n$ imply strong connectivity?
1 2 3 4 5