## Convex quadratic approximation to binary linear programming

Munapo (2016, American Journal of Operations Research, http://dx.doi.org/10.4236/ajor.2016.61001) purports to have a proof that binary linear programming is solvable in polynomial time, and hence that P=NP.

Unsurprisingly, it does not really show this.

Its results are based on a convex quadratic approximation to the problem with a penalty term whose weight $$\mathcal{l}$$ needs to be infinitely large for the approximation to recover the true problem.

My questions are the following:

1. Is this an approximation which already existed in the literature (I rather expect it did)?
2. Is this approximation useful in practice? For example, could one solve a mixed integer linear programming problem by homotopy continuation, gradually increasing the weight $$\mathcal{l}$$?

Note: After writing this question I discovered this related question: Time Complexity of Binary Linear Programming . The related question considers a specific binary linear programming problem, but mentions the paper above.

## Whether following language is linear or not?

I have a language $$L= \{a^nb^nc^m : n, m \ge 0\}$$.

Now, I wanted to determine whether this language is linear or not.

So, I came up with this grammar:

$$S \rightarrow A\thinspace|\thinspace Sc$$

$$A \rightarrow aAb \thinspace | \thinspace \lambda$$

I’m pretty sure(not completely however) that this grammar is linear and consequently language too is linear.

Now, when I use pumping lemma of linear languages with $$w$$, $$v$$ and $$u$$ chosen as follow I find that this language is not linear.

$$w = a^nb^nc^m, \space v = a^k, \space y=c^k$$

$$w_0 = a^{n-k}b^nc^{n-k}$$

now, $$w_0 \notin L \space (\because n_a \neq n_b)$$

So, I’m unable to find whether the language is linear or not and what goes wrong in above logic with either case. Please help.

## Help with Linear recurrence relation with balanced partition

In my slides for my algorithms class, I have a method of finding complexity of recursive functions called Recurrence Relation with “partizione bilanciata” which means “balanced partition”

My course is in Italian and looking online in English I could not find any trace of this method, I know of the recursive tree, induction and master theorem .

Has anyone an idea of how this is called in English ? I don’t like studying in Italian and I do not understand those pdfs.

I’m attaching some images of the formulas.

What exactly “balanced partition” mean, does it have something to do with for example Quick Sort , when you choose a middle pivot and the partitions are equal in size, which means it’s balanced ?

Is it the same as master theorem written maybe in a different way ?

Edit : I can see the form of the recurrence relation is different than master’s theorem.

When for master’s theorem instead of $$c*n^b$$ we have $$f(n)$$

Thank you

## Linear Programming with constrained sum of rows and sum of columns

Is there a structure to the solution of the following linear program?

$$\min_{x_{ij} } \sum_{i,j} x_{ij} \mu_{ij}$$

$$s.t. \forall j, \sum_{i} x_{ij} = \beta_j,$$ row sum

$$\forall i, \sum_{j} x_{ij} D_{ij} \leq 1,$$ column sum

## Constant vs linear time given knowledge of input distribution

Question about computer science whether a problem is O(1) or O(N). This was a thought experiment I came up with and I’m sure it’s rather basic. But I wasn’t sure how to look it up so I apologize if this is already posted on here somewhere. But I was wondering … let’s say we have a simple question: given a string of random integers, is there any number that’s greater than a certain threshold value in the series, if that would be a linear or constant time Big O? Now the small twist is that the distribution of the input would be known for example let’s say we want to look at a series of N numbers to see if one is at least N/2. If yes, boom we are done. And let’s say the numbers are positive integers bounded to N so all n < N. Given we know this distribution does it change if it is O(1) or O(N)? If we have a very long string of numbers then of course it is possible that no number meets the threshold but this becomes a much smaller and smaller and smaller possibility for a long series of such random numbers. Does it make a difference if the N/2 threshold is some constant integer value less than N?

## 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?

## How to detect infinite loop exist in linear bounded automata (LBA)?

The following theorem from Michael Sipser’s book “Introduction to the Theory of Computation” states:

$$A_{\textrm{LBA}}= \{ \langle M, w \rangle \mid \text{ M is an LBA that accepts string w } \}$$.

THEOREM: $$A_{\mathrm{LBA}}$$ is decidable.

On the proof part, it states:

The idea for detecting when $$M$$ is looping is that as $$M$$ computes on $$w$$, it goes from configuration to configuration. If $$M$$ ever repeats a configuration, it would go on to repeat this configuration over and over again and thus be in a loop.

I do not understand this: “If $$M$$ ever repeats a configuration, it would go on to repeat this configuration over and over again”. What if $$M$$ only repeat one configuration, then halts?

## How to input random values (constraints) of any variables in case of formulating Linear Programming Problem?

Suppose, Min 2x+3y Subject to, x=2,x=5,x=7 y=5, y=9 is a linear program. Where x holds the values 2 or 5 or 7 and y holds the values 5 or 9. Then what should the correct formulation for the above problem?

## If Then Constraint Linear Programming

I want to write the following constraint: If A=1 and B <= m then C=1 ( where A and C are binary, m is a constant and B is continuous).