2d
comment The relationship between degree of vertex and size of dominating set
Yes, that is correct. The bound should be $n H_{d+1}/(d+1)$ where $H_k$ is the $k$'th harmonic number. $H_{d+1}$ is at most $1 + \ln (d+1)$. Hence this bound matches what Florent posted in the answer below.
Feb
4
comment The relationship between degree of vertex and size of dominating set
Another way to see the bound is by observing that if you can obtain a fractional solution to the dominating set by setting a value of $1/(d+1)$ on each vertex where $d$ is the minimum degree. The total value of this fractional solution is $n/(d+1)$ and it is easy to see that it is feasible. Now by randomized rounding or known integrality gap results there is an integral solution of value $n\ln n/(d+1)$.
Feb
4
comment The relationship between degree of vertex and size of dominating set
Is there any reason to believe that the log n factor can be removed? I suspect that it may be necessary.
Jan
31
comment Minimizing a monotone submodular function under a cardinality constraint
There is a strong lower bound for this problem even in the monotone case. See arxiv.org/abs/0805.1071
Jan
29
comment Set Cover variant- improvement over log(n) approximation?
You can add dummy elements and essentially make all set sizes be roughly the same. Then you will be back to the difficult case of set cover with unit weights.
Jan
29
comment Solve the recurrence $f(n) = f(n-1) + f(n - \log n)$
What do you get if you try $f(n) = 2f(n - \log n)$? It appears that you will get a lower bound of $2^{\Omega(n/\log n)}$.
Jan
21
comment Which is the approximation class of Minimum 0-1 integer programming if only non-negative integers are allowed?
Take a closer look.
Jan
20
answered Which is the approximation class of Minimum 0-1 integer programming if only non-negative integers are allowed?
Jan
2
comment Fractional but not integer multi-commodity minimum cost flow
Schrijver's book on Combinatorial Optimization discusses several aspects of multiflows in Vol C.
Dec
6
comment Who are active researchers in the scheduling theory?
I guess this is not a research level technical question which explains the down voting. Perhaps a different forum exists for this question?
Dec
5
answered Who are active researchers in the scheduling theory?
Nov
27
comment Empty sudoku and NP-completeness
There is a minor technicality here. To specify an empty sudoku grid all we need to specify is the size of the puzzle. A sudoku puzzle is parameterized by $$n$$ and the size itself is a $$n^2 \times n^2$$ grid. However, specifying $$n$$ takes only $$\log n$$ bits while the solutions requires writing down $$n^2 \times n^2$$ numbers.
Nov
17
answered Problems in quasi-polynomial time that could conceivably be in P (without causing collapses or violating widely held beliefs)
Oct
20
comment Sum-of-squares proof system
Laserre has a recent book on the optimization aspects. "An Introduction to Polynomial and Semi-Algebraic Optimization" published by Cambridge University Press.
Oct
7
comment Decide whether a point is a vertex of a polytope?
Given a polytope $P$ and a point $x$ one can write $x$ as a convex combination of vertices of $P$ in polynomial time iff one can optimize or separate over $P$. This should help address your problem, I think.
Sep
17
comment Finding the longest path between two nodes in a bidirectional unweighted graph
I also recommend looking at Gabow's algorithm which finds in polynomial time paths that are longer than log n. However it works only for undirected graphs. epubs.siam.org/doi/abs/10.1137/…
Sep
13
awarded Revival
Sep
13
revised What is the complexity of minimum weight odd T-join?
deleted 34 characters in body
Sep
12
comment Is it still open to determine the complexity of computing the treewidth of planar graphs?
Regarding the problem of approximating treewidth. An $\alpha$-approximation for finding sparse/balanced node-separators will give an $O(\alpha)$-approximation for treewidth. Thus, in general graphs we will get $O(\sqrt{\log n})$ via ARV/Feige-Lee-Hajiaghayi and $O(1)$ in planar and proper minor-closed families. For general graphs one can get $O(\sqrt{\log k})$ where $k$ is treewidth.
Sep
2
comment Maximum size-k cut
Max-Cut is a symmetric submodular function. For symmetric non-negative functions there is a better than 1/e approximation due to a recent result of Moran Feldman. See arxiv.org/pdf/1409.5900.pdf
1 2 3 4 5