Proving inequalities related to Dijkstra’s algorithm

Define $ spdist(s,t)$ as the distance of the shortest path from vertex $ s$ to $ t$ .

Define $ IN(v)$ as the set of in-neighbors of $ v$ .

Define $ w(u,v)$ as the weight of the edge $ (u,v)$ .

I am asked to prove the following two inequalities to gain the correctness of Dijkstra’s algorithm:

$ $ spdist(s,v)\leq min_{u \in IN(v)} \{spdist(s,u)+w(u,v)\}$ $

and

$ $ spdist(s,v)\geq min_{u \in IN(v)} \{spdist(s,u)+w(u,v)\}$ $

For the ≤ direction, it is quite obvious. Since we must go through either one of the edge $ (u,v)$ to reach $ v$ , $ spdist(s,v)$ is by definition smaller or equal to the RHS.

However, I am having trouble proving the ≥ direction. May I have some intuition of tips on how to prove the ≥ direction?

Thanks!

Linear programs with strict inequalities and supremum objectives

Linear programming can solve only problems with weak inequalities, such as “maximize $ c x$ such that $ A x \leq b$ “. This makes sense, since problems with strict inequality often do not have a solution. For example “maximize $ x$ such that $ x<5$ ” does not have a solution.

But suppose we are interested in finding supremum instead of maximum. In this case, the above program does have a solution – the supremum is $ 5$ .

Given a linear program with strict inequalities and a supremum or infimum objective, is it possible to solve it by reduction to a standard linear program?

Doubts in some inequalities used in asymptotic analysis

I was going through this recent paper, and I had a couple of doubts in the final analysis of complexity of the scheme (you don’t need to go through the whole paper). I included three questions here, as I thought they seem to simple questions.

  1. In Pg 17 (last four lines, see after equation 7), there is this inequality that is used (here, $ k(n) = \sqrt{\frac{n\delta(n)}{\log n}}$ and $ \delta(n) = o(n / \log n)$ ):

$ \frac{\binom{n}{a}}{\binom{^n/_k}{^a/_k}^k} \leq (^n/_k)^k$

Can I know a proof for it?

  1. Similarly, in the beginning of Pg 18, how is this possible? (the above inequality is used to get here though, $ (n / k)^{k / 2}$ thing, and don’t worry about the meaning of $ \mathtt{ss}$ )

$ \mathtt{ss} \leq \sqrt{\binom{n}{\frac{n}{2}-\delta(n)}}\cdot (n / k)^{k / 2} \cdot \binom{k}{2\delta(n)} \cdot 2^{(2\delta(n)+1)n / k} \leq 2^{n / 2 + o(n)}$

  1. Also, this one might be a bit trivial, in Pg 17, one inequality above equation 7, the $ O(n)$ term is dropped, isn’t that relevant?

Bridging between Rosethal Inequalities and log convex tails

Let $ X_1,\ldots,X_n$ be independent with $ \mathbf{E}[X_i] = 0$ and $ \mathbf{E}[|X_i|^t] < \infty$ for some $ t \ge 2$ . Write $ \|X\|_p = (E|X|^p)^{1/p}$ .

Then we have the classical “Rosenthal-type inequalities”: $ $ \left\|\sum_i X_i \right\|_p \le C_1\left(\sqrt{p}\left(\sum_i \|X_i\|_2^2\right)^{1/2} + p\left(\sum_i \|X_i\|_p^p\right)^{1/p}\right), \ \left\|\sum_i X_i \right\|_p \le C_2\frac{p}{\log p}\left(\left(\sum_i \|X_i\|_2^2\right)^{1/2} + \left(\sum_i \|X_i\|_p^p\right)^{1/p}\right) \ \text{and in general} \ \left\|\sum_i X_i \right\|_p \le C_3\min_{s=1}^p\left(\sqrt{s}e^{p/s}\left(\sum_i \|X_i\|_2^2\right)^{1/2} + s\left(\sum_i \|X_i\|_p^p\right)^{1/p}\right) $ $

On the other hand, if $ X_i$ all have logarithmically concave tails; (that is, $ \Pr[X \ge t = e^{−N(t)}]$ for $ t \ge 0$ , where $ N : R_+ \to R_+ \cup\{\infty\}$ is a convex function), then we have the much stronger:

$ $ \left\|\sum_i X_i \right\|_p \le C_4\left(\sqrt{p}\left(\sum_i \|X_i\|_2^2\right)^{1/2} + \left(\sum_i \|X_i\|_p^p\right)^{1/p}\right). $ $ (Note there is no factor $ p$ on the second term.)

My question is thus: Is there a series of results interpolating between the Rosenthal inequalities and the inequalities for heavy random variables?

It creates an odd “discontinuity” that the factor of $ p$ disappears suddenly when the random variables get sufficiently heavy.

Interestingly, for identical random variables we can use the theorem $ $ \left\|\sum_i X_i \right\|_p \le C_5 \sup_{\max\{2,p/n\}\le s\le p}\frac{p}{s}\left(\frac{n}{p}\right)^{1/s}\|X_1\|_s $ $ to show that $ \|X\|_p \le p^c \implies \left\|\sum_i X_i \right\|_p \le C_6(\sqrt{pn} + (n/p)^{1/p}p^c)$ for any $ c>0$ , $ p\le n$ . This can be interpreted as saying that the $ p$ -free version of the above inequalities is true in many cases, even when the random variables aren’t that heavy.

(I should note that all results listed in this question can be found in Rafał Latała’s: https://www.mimuw.edu.pl/~rlatala/papers/AOPSUMS97.pdf)

Automating the solution of pairs of polynomial inequalities as a bound

Let’s consider the following pair of quadratic inequalities:

$ $ x^2+x \geq a$ $

and

$ $ x^2-x < a$ $

The solution of the first inequality is $ $ x \geq \frac{-1+ \sqrt{1+4a}}{2}$ $ or $ $ x \geq \frac{-1- \sqrt{1+4a}}{2}$ $ .

Now, the first one is always going to be larger than the second one, as $ $ \sqrt{1+4a}>0$ $ . So, $ $ x \geq \frac{-1+ \sqrt{1+4a}}{2}$ $ is the “true” lower bound. Therefore, we will consider the solution as:

$ $ x \geq \frac{-1+ \sqrt{1+4a}}{2}$ $ ——> (1)


For the second inequality, the solution is $ $ x < \frac{1+ \sqrt{1+4a}}{2}$ $ or $ $ x < \frac{1- \sqrt{1+4a}}{2}$ $ .

Again, since $ $ \sqrt{1+4a}>0$ $ , the second solution is always going to be smaller than the first solution. So, $ $ x < \frac{1- \sqrt{1+4a}}{2}$ $ is the “true” upper bound.

However, because $ $ \frac{1- \sqrt{1+4a}}{2}$ $ is negative of the solution of the first inequality from (1), we encounter some issues. For example, if the solution in (1) is negative (<0), then its fine. For example, if, say, (1) evaluates to $ $ x \geq -5$ $ , then our solution to the second inequality implies $ $ x<5$ $ , which is fine. But, if the solution in (1) is positive (>0), then the pair of solutions taken together doesn’t make sense. For example, if (1) evaluates to $ $ x \geq 5$ $ , then our solution to the second inequality implies $ $ x<-5$ $ , which is nonsensical.

Therefore, we need to reject this solution for the second inequality and accept the other solution as the true solution:

$ $ x < \frac{1+ \sqrt{1+4a}}{2}$ $ ——> (2)

Thus, from (1) and (2), we can say that the solution of these 2 inequalities given as a bound is:

$ $ x \in [\frac{-1+ \sqrt{1+4a}}{2}, \frac{1+ \sqrt{1+4a}}{2})$ $


As demonstrated, the process of rejecting 2 of the possible solutions can be a bit involved. Also, the process can be different for other sets of inequalities, where the same lines of thinking might not disqualify 2 of the candidate solutions.

I want to be able to automate this process for any pair of inequalities. I have written the following code to solve a set of quadratic polynomial inequalities and return the solution as a bounded set:

from sympy import simplify, degree import math  def extract_terms(LHS, operator, var):     expression = simplify(LHS)     variable  = simplify(var)     poly_degree  = degree(expression, gen=variable)      term_coeffs = []     for x in range(poly_degree,-1,-1):         if x>0:             term = simplify(str(variable)+"**"+str(x))             term_coeffs.append(expression.coeff(term))             expression = simplify(str(expression)+"-"+str(simplify("("+str(term)+")*("+str(expression.coeff(term))+")")))         else:             const_value =  expression             term_coeffs.append(const_value)     return term_coeffs  def solve_quad_inequality(LHS, operator, var):     c, d, e = extract_terms(LHS, operator, var)     try:         s1 = -(d/(2.0*c))+math.sqrt(-(e/c)+(d/(2.0*c))**2)         s2 = -(d/(2.0*c))-math.sqrt(-(e/c)+(d/(2.0*c))**2)         return s1, s2     except:         print('The given inequality does not have a real solution.')         return 0  def give_soln_bounds(LHS_1, operator_1, var, LHS_2, operator_2):     s1a, s2a = solve_quad_inequality(LHS_1, operator_1, var)     print("The candidate solutions for {}{}0 are: {}{}{} or {}{}{}".format(LHS_1, operator_1, var, operator_1, s1a, var, operator_1, s2a))      s1b, s2b = solve_quad_inequality(LHS_2, operator_2, var)     print("The candidate solutions for {}{}0 are: {}{}{} or {}{}{}".format(LHS_2, operator_2, var, operator_2, s1b, var, operator_2, s2b))      a = s1a if s1a>=s2a else s2a     if s1b<s2b:         if s1b>a:             b = s1b         else:             b = s2b     else:         if s2b>a:             b=s2b         else:             b=s1b      print('The bounded solution for the given pair of inequalities is: x ∈ ['+str(a)+', '+str(b)+')')  give_soln_bounds("x**2-5*x+6", ">=", "x", "x**2-5*x+4", "<") 

This gives the following output:

The candidate solutions for x**2-5*x+6>=0 are: x>=3.00000000000000 or x>=2.00000000000000 The candidate solutions for x**2-5*x+4<0 are: x<4.00000000000000 or x<1.00000000000000 The bounded solution for the given pair of inequalities is: x ∈ [3.00000000000000, 4.00000000000000) 

Another example test:

give_soln_bounds("x**2+x-1", ">=", "x", "x**2-x-1", "<") >>>  The candidate solutions for x**2+x-1>=0 are: x>=0.618033988749895 or x>=-1.61803398874989 The candidate solutions for x**2-x-1<0 are: x<1.61803398874989 or x<-0.618033988749895 The bounded solution for the given pair of inequalities is: x ∈ [0.618033988749895, 1.61803398874989) 

It seems to work fine for the examples I have thrown at it so far, but is there any way to know if its truly correct? Any counterexample would be great too!

Also, it can’t handle equations where I give symbolic inputs. For example, $ $ x^2-x-k<0$ $ , where the solution is expected in terms of k. Is there any way to do that?

Another issue is, if I want to this for cubic inequalities, I can foresee a problem with comparing all the 9 possibilities arising from the 3 candidate solutions for each inequality. Is there any way to cut down on the number of comparisons to be made to search for the valid solutions?

And finally, if you see any possible improvement in the code (be it style-wise or performance-wise), please do let me know.

Is there a software to solve function inequalities?

Suppose I have some inequalities that my function (say $ \mathbb R\to \mathbb R$ ) needs to satisfy, like $ \forall x,y\; f(x)+f(y)\le f(x+y)$ and $ f(1)=0$ . Is there some software that can find solutions/prove that there’s no such function?

Of course, the problem is undecidable in general, but this doesn’t rule out some software that could be efficient in practice.