All Questions
2,368 questions
0
votes
0
answers
194
views
A linear program related question
Dear all, recently, I encountered the following problem. It is closely related to the order of growth for UMD constants of all $n$-dimensional Banach lattice.
Let $\alpha^k \in (\alpha_1^k, \alpha_2^...
- 769
0
votes
0
answers
79
views
Computing maximum point for minimal function of a family of linear functions
Let $x \in S^n $ where $S^n = ${$ [x_1,x_2,...,x_{n+1}]\in \mathbb{R}^{n+1} \mid x \ge 0 , \sum x_i = 1 $} and let $f_i : I^n \to \mathbb{R}$ be a finite $m$-sized family of LINEAR functions such that:...
- 11
0
votes
0
answers
783
views
LP relaxation for ILP\IP (integer linear programming)
I am familiar with LP relaxation for ILP (or IP). Assume we concern with integer minimization problem, which we formalize using ILP; we then relax the ILP into LP and we say that the LP provides a ...
0
votes
0
answers
167
views
Centrally symmetric neighborly polytopes
Let $P$ be a centrally symmetric $k$-neighborly $d$-polytope. Let $ P^* $ is polar (also dual) of $P$. Consider a polytope $Q^*$ , $Q^* \subset P^* $(not necessarily a face of $P^*$). By duality,
$P\...
- 31
0
votes
0
answers
113
views
Question regarding contiguous forms
I read about contiguous forms in Achill Scürmann's thesis on positive quadratic forms. I am wondering about one aspect of the Voronoi algorithm presented in there, that enumerates all arithmetically ...
- 149
0
votes
0
answers
118
views
sparsest cut always has solution
Hi!
How to prove that sparsest cut always has an optimal solution which is the cut for some vertex-subset.
Looks like it's should be a kind of fundamental theorem for sparsest cut. But I didn't ...
- 1
0
votes
2
answers
102
views
Does Max Flow produce uniform results? [closed]
I am interested in using Max Flow algorithm. I want to simulate transfer of quantity. Anyway, I am unsure of some thing.
Does Max Flow algorithm produce uniformly distributed max flow?
I have ...
- 11
-1
votes
1
answer
268
views
Walks that cannot hit the boundary
I've casually proved, as application of some ideas that I am developing, a result that might be of interest in itself. I am completely new in this field and then I would like to ask your help to ...
- 6,034
-1
votes
2
answers
114
views
On OR condition in Linear Programming with exponentially many constraints [closed]
Suppose we have two linear programs $Ax\leq b$ and $Bx\leq c$ is there a way to combine them into one program of possibly a larger dimension $Cy\leq d$ such that projection of vectors $y$ into a ...
- 13.9k
-1
votes
1
answer
137
views
Does a half plane contain intersection of some other half planes? [closed]
I'm doing research in Optimization and I have found this obstacle in the way.
If we have set of half planes like $c_ix\leq b_i$ where $i\in \{1,\ldots ,k\}$ there is an algorithm(it would be better ...
- 19
-1
votes
1
answer
103
views
How to solve MILP problem on several linear subspaces
I have a set of close mixed-integer programming problems. More exactly, all the problems share the same set of (binary and continuous) variables, the same set of linear inequality constraints, and the ...
- 39
-1
votes
1
answer
96
views
On bounding a certain discrepancy between probability distributions on the symmetric group
Disclaimer. This is a follow up to a question I asked and answered on SE https://math.stackexchange.com/q/3579311/168758. The question was about upper-bounds. Here I'm interested in lower bounds, and ...
- 6,853
-1
votes
1
answer
88
views
sparse data fitting problem [closed]
I am a new learner of optimization, and I am confused by the question below, (how to change a 0-norm constrain into binary and linear constrain ?)
Given a sparse data fitting problem:
$ minimize \...
- 1
-1
votes
1
answer
96
views
Chromatic Number of graph of a set of squares [closed]
We are given a set of squares in the plane with sides parallel to the x-y axes.
We know that intersection of every three of them is empty.
Show that we can color these squares with red, blue and ...
- 1
-1
votes
1
answer
502
views
How to formulate such problem mathematically? (line continuation search) [closed]
I have an array of "lines" each defined by 2 points. I am working with only the line segments lying between those points. I need to search lines that could continue one another (relative to ...
- 13
-1
votes
0
answers
41
views
Is it possible to backtrack an optimization solver? [closed]
I have an optimization problem and was using a linear programming optimizer to find solutions. However, I find that past a certain size, the problem becomes "infeasible" and has no solutions....
-2
votes
1
answer
141
views
Solution to Erdos-Ulam problem [closed]
I have solved the Erdos-Ulam problem (see link) and can construct a set that satisfies the conditions (dense in R2 with all interpoint distances rational). I have expanded the solution from two ...
-3
votes
1
answer
952
views
combinatoric proof $\sum_{i=0}^{n}(-1)^i\binom{n}{i}\binom{n-i+k-1}{k}=\binom{k-1}{k-n}$ [closed]
I would like help with combinatorial proof ,
not algebraic proof . Thank you for your time
$\sum_{i=0}^{n}(-1)^i\binom{n}{i}\binom{n-i+k-1}{k}=\binom{k-1}{k-n}$
- 103