User norouzi - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T10:25:43Z http://mathoverflow.net/feeds/user/19394 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/115558/convex-upper-bound-on-a-linear-fractional-function Convex upper bound on a linear-fractional function Norouzi 2012-12-05T23:18:34Z 2012-12-07T05:23:19Z <p>I have a function of the form $f(x,y) = \frac{x}{c+y}$ where $c$ is a positive constant, $c \ge x \ge 0$, and $y \ge 0$. I would like to find a convex upper-bound for this function. Is there a principled way for doing this? How about if the upper-bound has to be convex and piecewise linear? Is there a way to find the optimal upper-bound in terms of the number of linear pieces?</p> <p>Update: Sorry I changed the boundary conditions on $x$ and $y$ so it suits my problem better.</p> http://mathoverflow.net/questions/115558/convex-upper-bound-on-a-linear-fractional-function/115627#115627 Answer by Norouzi for Convex upper bound on a linear-fractional function Norouzi 2012-12-06T16:29:47Z 2012-12-06T16:29:47Z <p>Not exactly the answer, but I think $g(x,y) = \frac{x^2}{(c+y)^2}$ is a reasonable convex lower-bound for $f$. With the assumption that $c \ge x$, then $1 \ge f(x,y) \ge 0$, and so $f(x,y)^2 \le f(x,y)$.</p> http://mathoverflow.net/questions/82332/seeking-a-solution-algorithm-to-the-3-partition-problem/82388#82388 Answer by Norouzi for Seeking a solution algorithm to the 3-partition problem Norouzi 2011-12-01T15:31:43Z 2011-12-01T16:22:13Z <p>There exists a pseudo-polynomial time dynamic programming solution to this problem, for which running time and storage complexity depend on the sum of costs of the pieces of jewelry, denoted $S$. If the sum of costs, $S$, is small then the algorithm would be practical as its storage is $O(S^2)$ and its running time is $O(S^2N)$, $N$ being the number of pieces (48 here).</p> <p>To get a sense of the algorithm take a look at the <a href="http://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-polynomial_time_dynamic_programming_solution" rel="nofollow">Subset sum problem Wikipedia page--dynamic programming solution</a>. This concerns finding a subset of items which sums to a particular cost. Clearly you can solve the 2-partition problem by using the subset sum solutions, i.e., by enumerating over all the potential subset sums, and choosing the one that you prefer for any reason.</p> <p>Now generalizing to 3-partition is straightforward. You basically solve the double-subset sum problem. You store $Q(i,s, t)$ to be the value (true or false) of "whether there are two disjoint subsets of $x_1, \ldots, x_i$ which respectively sum to $s$ and $t$". You can easily update $Q(i, s, t)$ by adding new items. Again one can enumerate over the potential $Q(N, s, t)$'s and choose the one that is considered best.</p> <p>Obviously even if $S$ is large, the costs can be quantized using larger cost units, which results in a measurable upper bound on the error. This also can be used combined with the solution of Brendan McKay to guide a local search algorithm.</p> http://mathoverflow.net/questions/81392/an-optimization-problem-involving-sum-of-binomial-coefficients-upto-some-value An optimization problem involving sum of binomial coefficients upto some value Norouzi 2011-11-20T03:16:20Z 2011-11-21T09:57:30Z <p>I would like to minimize $f(s, n, \epsilon)$ with respect to $s$ where $$f(s,n,\epsilon) = \left( 1 + \frac{n}{2^s} \right)\frac{1}{s} \sum_{k=0}^{\lfloor s\epsilon \rfloor} {s \choose k}~.$$ Note that $0 &lt; \epsilon &lt; \frac{1}{2}$ and $n > 0$. Clearly optimal $s$ is going to be a function of $\epsilon$ and $n$, which might be ugly. However, I think $s^*$ should be close to $\log_2{n}$, based on the intuition from the problem giving rise to this, but I cannot find any rigorous argument for this choice of $s^*$. Any hint or idea is highly appreciated.</p> <p>The following upper bound might be helpful: $$\sum_{k=0}^{\lfloor s\epsilon \rfloor} {s \choose k} \le 2 ^ {H(\epsilon)s }$$ where $H(\epsilon) \equiv -\epsilon \log \epsilon -(1-\epsilon) \log(1-\epsilon)$; the entropy of a Bernoulli dist. with probability $\epsilon$. </p> <p>I don't know of any clean lower bound. Any idea?</p> <p>Thanks for your time in advance.</p> http://mathoverflow.net/questions/115558/convex-upper-bound-on-a-linear-fractional-function Comment by Norouzi Norouzi 2012-12-06T03:17:52Z 2012-12-06T03:17:52Z The function f is quasiliner. It has convex parts eg. when one sets $x=1$ and only varies $y$, $f(x,y) = f(y) = \frac{1}{c+y}$, and concave parts, eg. when one sets $y = x$, and so $f(x,y) = f(x) = \frac{x}{c+x}$. I would like to find a convex upper-bound for $f$ if possible. http://mathoverflow.net/questions/81392/an-optimization-problem-involving-sum-of-binomial-coefficients-upto-some-value/81418#81418 Comment by Norouzi Norouzi 2011-11-21T02:49:24Z 2011-11-21T02:49:24Z Thanks! How about if n or s doesn't go to infinity. Can we still say something? http://mathoverflow.net/questions/81392/an-optimization-problem-involving-sum-of-binomial-coefficients-upto-some-value Comment by Norouzi Norouzi 2011-11-21T01:03:51Z 2011-11-21T01:03:51Z Great! Let me know if you have some insight.