All Questions
1,809 questions
1
vote
0
answers
25
views
Reporting uncoverable directed simple cycles in digraphs
What is known about cycles in digraphs that can't be member of any of that digraph's vertex disjoint directed cycle covers as illustrated below?
in that "cat's eye graph" the green cycle ...
- 13.2k
1
vote
0
answers
46
views
Computational complexity of rate $\frac{1}{2}$ codes
We know from Berlekamp, McEliece and Van Tilborg [On the inherent intractability of certain coding problems, IEEE Trans. Information Theory, 24 (1978)] that computing the minimum distance of a (binary)...
- 71
1
vote
0
answers
118
views
Promise version of minimum distance
It has been known for some time that computing minimum distance of a linear code (minimum weight codeword) is NP-hard.
This immediately also says that given a code $C$, calculating minimum hamming ...
- 71
1
vote
0
answers
163
views
Optimization problem on trace of complex matrix product
Given a complex rectangular matrix $A$ $(k \times n)$, I am interested in solving the following optimization problem over $(k\times n)$ complex matrices $x$:
$$
\mathrm{arg}\max_X \,\mathrm{trace}(X^...
- 377
1
vote
0
answers
63
views
Counting $\bmod 2$ number of vertices of sparsely represented polyhedra
Given a polyhedron
$$Ax\geq b$$
is there an $NC^1$ or an $NC^2$ algorithm to count the number of vertices $\bmod2$?
Assume $A\in\{0,1\}^{m\times n}$ and $b\in\mathbb Z^{m}$ ($m=O(n)$) and assume rows ...
- 13.9k
1
vote
0
answers
43
views
Detecting non-negativity of a single constraint by polyhedral constraints - $II$
Let $$\langle a,x\rangle=b$$ be a linear constraint where $x\in\mathbb R^n$ and every entry in $a=(a_1,\dots,a_n)$ is in $\mathbb Z_{\geq0}^{n}$ (non-negative) and the entry $b$ is in $\mathbb Z_{\...
- 13.9k
1
vote
0
answers
209
views
Solution to system of linear equations
Input: System of linear equations $$A[x_1,\dots,x_{t}]=b$$ where number of equations is at least number of variables but independence is not guaranteed. However there is atmost one non-negative ...
- 13.9k
1
vote
0
answers
122
views
Integrality of polyhedra
Given two polyhedra in $H$ representation $P_1:Ax\leq b$ and $P_2:Bx\leq c$ which are integral are bounded when is their intersection also integral?
Given two polyhedra in $H$ representation $P_1:Ax\...
- 13.9k
1
vote
1
answer
115
views
$\mathrm{LP}$ formulation for $\mathrm{k}$-$\operatorname{opt}$ moves
$\mathrm{k}$-$\operatorname{opt}$ moves are an idea to improve non-optimal Hamilton cycles in weighted symmetric graphs by exchanging $\mathrm{k}$ tour-edges with $\mathrm{k}$ edges that do not belong ...
- 13.2k
1
vote
0
answers
172
views
continuity of linear programming
I have the following conjecture:
Given a closed convex set $S \subseteq \mathbb{R}^n$ and one of its exposed face $F=\{x \in S \mid \pi x = \pi_0\}$, where $\pi x =\pi_0$ is the supporting hyperplane ...
- 37
1
vote
0
answers
81
views
Algorithm for deciding feasibility of linear programs [closed]
Suppose I have the simple linear program
$$Ax \geq 0, \quad x \geq 0$$
We know that this system has a solution (for example, $x=0$). But, what if we made this rule for this system?
$$Ax \geq 0, \quad ...
1
vote
0
answers
920
views
Maximizing a piecewise-linear convex function
Crossposted on Operations Research SE.
I am working on an optimization problem where some of the terms of the objective function to maximize are expressed as a piecewise linear function of variables:
...
- 111
1
vote
0
answers
62
views
Complexity of checking if a set is an additive basis
A set of nonnegative integers $A$ is said to be an additive basis of order $k$ if every nonnegative integer is equal to the sum of $k$ elements of $A$. For example, Lagrange's theorem says that the ...
- 71
1
vote
0
answers
323
views
Decomposition of Polyhedral - An example
There is no doubt that clear examples consolidate the understanding of concepts being learnt. I am new to finding the structure and decomposition of a polyhedra. Suppose that we have the system
$$ \...
- 111
1
vote
0
answers
78
views
$\mathsf{NP}$ complete version of Skolem arithmetic
Definable subsets of $\mathbb N$ in the language of Presburger arithmetic are exactly the eventually periodic sets and quantifier free part corresponds to Integer Programming with linear inequalities.
...
- 13.9k
1
vote
0
answers
176
views
Reduction graph isomorphism to maximum independent set in very dense graph
We got a reduction graph isomorphism to MIS in a very dense graph,
or alternatively negative monotone 2-CNF to MAX-ONEs with a formula
with many clauses.
Let $G,H$ be graphs of order $n$ and adjacency ...
- 25.4k
1
vote
2
answers
267
views
Optimal path with multiple costs
Given a graph $G=(V,E)$, each edge $e$ has $k$ costs $c_i(e)$, $1\le i\le k$. Correspondingly, a path $P$ is also characterized by $k$ costs where $c_i(P)=\sum_{e\in P} c_i(e)$. Given vertices $s$ and ...
- 367
1
vote
0
answers
47
views
Restriction of Rademacher Complexity
Let $F\subseteq C([0,1]^n,\mathbb{R})$ be a finite family of functions, which is non-empty. Let $A,B$ be subseteq of $[0,1]^n$, again non-empty, and let $Rad(C)$ denote the Rademacher complexity of ...
- 5,405
1
vote
0
answers
89
views
Polynomial time for a quadratic equation and linear inequalities?
Does anyone know how to find a feasible solution (or the infeasibility of any solution) in a polynomial time to the following problem:
\begin{align*}
xAx^t = 0, \\
Bx^t = c, \\
x_i \ge 0,
\end{align*}
...
- 11
1
vote
0
answers
68
views
Fundamental regions in convex programming
In linear programming, the fundamental regions are polyhedra, since those are the intersection of half-spaces defined by linear inequalities. In semidefinite programming, the fundamental regions are ...
- 13.9k
1
vote
0
answers
148
views
Convergence of infinite linear programming
Suppose we have the following linear program (LP1),
$$\min_{f \in \mathcal{C}} \int_{\mathbb{R}} f(t) \cos(2 \pi x_0 t) dt \\ \text{subject to } \int_{\mathbb{R}}f(t)dt = 1 \\\forall x\in [0,1]: \int_{...
- 53
1
vote
0
answers
104
views
Meaning of L-reduction from Dominating set problem
We are working in a variation of Locating dominating sets. Recently, we realized that the reduction from dominating set to our problem in proving its NP-completeness turns out to be also an L-...
- 11
1
vote
0
answers
82
views
What is the relation between different generalizations of linear programming?
Linear programming subsumed by each of
Semidefinite programming (SDP)
Convex programming (CXP)
SOS programming (SSP)
Is there any relation between each pair in the three?
Are all three equivalent in ...
- 1,826
1
vote
0
answers
144
views
Checking existence of proofs of fixed length
This question is a continuation of a related previous question (check here).
Let $\mathcal{L}$ be a recursive first-order theory with the Hilbert-Ackerman's proof calculus, and such that the ...
- 3,318
1
vote
0
answers
147
views
The chromatic polynomial of a line graph
Is there a way to obtain the chromatic polynomial of the line graph of a regular simple graph, having known the chromatic polynomial of the graph?
There already exist characterizations of line graph ...
- 2,089
1
vote
0
answers
78
views
Reference for the algorithm to find the intersection between a subspace and positive orthant
I came across this algorithm, in this question Algorithm for the intersection of a vector subspace with a cone of non-negative vectors ;
Is there any reference for the algorithm described in the ...
1
vote
0
answers
67
views
What are the corners of this polytope?
Let $f$ be a non-negative function on the positive integers such that $f(s+t)\geq f(s) + f(t)$ for all $s,t\in\mathbb{Z}^+$. Consider the polytope consisting of all $x\in \mathbb{R}^n$ such that $$\...
- 11
1
vote
0
answers
28
views
Modified straightline complexity of almost square of sums
Assume every linear operation (such as inner product with constant vector) can be performed in one step and multiplication by variables (quadratic operation) can be performed in one step.
We know the ...
- 1,826
1
vote
0
answers
1k
views
Computational complexity of computing the trace of a matrix product under some structure
I have two problems related to computing some trace, and some (possibly suboptimal) answers. My question is about a potential more efficient algorithm for each one. (More interested in an answer to ...
- 123
1
vote
0
answers
127
views
Does relationship between c.e.set, productive set, immune set, ML-random set exist between sets of class of other level
Is relationship between c.e.set, productive set, immune set, ML-random set similar to relationship between polynomial complexity set, polynomial complexity-productive set, P-immune set, P-random set?
- 3,094
1
vote
0
answers
283
views
total unimodularity of a matrix
Let G be the node-arc incidence matrix of a given directed network (rows of $G$ correspond to nodes and its columns correspond to arcs). Let $B_1,\dots, B_K$ denote a partition of the nodes of the ...
- 393
1
vote
0
answers
45
views
Coloration of an interval graph with constraints [closed]
Given an interval graph that represents a set of tasks, in a given period of time, to be assigned to a set of employees, the objective is to find a minimum coloring of this graph such that the total ...
- 11
1
vote
0
answers
78
views
Deciding if a set of hyperplanes passes through a point
There is a set of vectors $\vec a_{k,i}$ with $k\in\{1,\dots,n\}$ and $i\in\{0,1\}$,
such that every $n+1$-tuple $\{\vec v_{1,s_1},\dots,\vec v_{n,s_n},\vec v_{r,1-s_r}\}$
is linearly independent for ...
- 1,207
1
vote
0
answers
76
views
Classically compute ahead time if Lie Algebra is either polynomial finite or geometrically closed?
Given a set of $N$ operators $\mathcal{O}$ with a known set of Lie Algebra group multiplication rules $\mathcal{G}$ that can be programmed into a classical computer, is there a classical poly($N$) ...
- 215
1
vote
0
answers
163
views
Can we reduce the maximization of this integral to the maximization of the integrand?
I would like to know whether we are able to reduce the following optimization problem to the pointwise optimization of the integrand (or how we can solve it otherwise): Maximize $$\sum_{i\in I}\sum_{j\...
- 167
1
vote
0
answers
25
views
Weird subspace/equality-constrained LP problem/variant of change-making problem
Assume that we have a set, $\mathscr{R}$ containing $m$-dimensional vectors. Solve
$$\sum_{i=1}^n c_i\leq\delta$$
$$\text{subject to } \sum_{i=1}^n r_i c_i=x^\prime \text{ for all }x^\prime$$
where
$0\...
- 11
1
vote
0
answers
222
views
Way to express a number in its most compact sum of powers
Given a non-negative number n, what is the best approach to find the most compact representation for n in terms of sums of powers, such that the bases and the exponents can't surpass a given value (...
- 11
1
vote
0
answers
177
views
Prove that these linear programming problems are bounded by $O(k^{1/2})$ [closed]
The expanded partial sums of the Möbius inverse of the Harmonic numbers have two out of three properties in common with this set of linear programming problems:
$$\begin{array}{ll} \text{minimize} &...
- 1,183
1
vote
0
answers
121
views
Calculate amount of FLOPs for an eigenvalue problem solver
I've got 2 complex, non symmetric, matrices $A_{1000x1000}$, $B_{1000x1000}$ and I am using Matlab to get it's eigenvalues (functions like eig or eigs). Both matrices are different - one is more dense ...
- 111
1
vote
0
answers
68
views
Projection of a polytope along 4 orthogonal axes
Consider the following problem:
Given an $\mathcal{H}$-polytope $P$ in $\mathbb{R}^d$ and $4$ orthogonal vectors $v_1, ..., v_4 \in \mathbb{R}^d$, compute the projection of $P$ to the subspace ...
- 11
1
vote
0
answers
36
views
Linear programming with a convergent coefficient
The following linear programming problem
$x_n = \arg\min c_n'x \mbox{ subject to } Ax<b$
has a changing coefficient $c_n$. We have that $c_n\rightarrow c_*$. What happens to the solution $x_n$? ...
- 19
1
vote
0
answers
126
views
Mixed integer formulation of union of polytopes?
Given $t$ different unbounded polyhedra $P_1:A^{(1)}x^{(1)}\leq b^{(1)},\dots,P_t:A^{(t)}x^{(t)}\leq b^{(t)}$ we are looking for the representation of $\bigcup_{i=1}^tP_i$ (not their convex hull) with ...
- 1,826
1
vote
0
answers
57
views
On divisibility conditions implying local coprimality conditions
This question is inspired by Bernardo Recaman's question Strings of consecutive integers divisible by 1, 2, 3, ..., N on intervals of $n$ integers being divisible by the integers $1$ through $n$. The ...
- 13k
1
vote
1
answer
248
views
Complexity class of chess when simulated by a Turing machine [closed]
Suppose we simulate the game of chess with a Turing machine $M$ as follows:
The semi-infinite input tape of $M$ contains a sequence of symbols beginning in the first cell of the tape. Each symbol ...
- 11
1
vote
0
answers
88
views
What is the probability of 'yes' to this likely $coNP$ problem?
Pick a set of primitive (gcd of coordinates is $1$) integer points $\mathcal T$ in $\mathbb Z^n$.
Denote the set of $n$ many algebraically independent homogeneous system of polynomials (thus zero-...
- 1,826
1
vote
0
answers
24
views
Simple monotonicity property for coordinate descent and linear objective functions
Let $S \subset \mathbb{R}^n$ satisfy $0\leq x_1\leq\dots\leq x_n$ for all $\mathbf{x}\in S$, among other (possibly nonconvex) constraints, and suppose in addition that $\sum_{i=1}^n x_i \geq 1$ for ...
- 4,049
1
vote
0
answers
37
views
Fast certficate of negativity for objective value of mixed-integer linear program
Let $c \in \mathbb R^n$, $A \in \mathbb R^{m \times n}$, $b \in \mathbb R^m$, and $I \subseteq \{1,2,\ldots,n\}$. Consider the Mixed integer linear program (MILP)
$$
\begin{split}
f^* = &\max \; ...
- 6,853
1
vote
0
answers
67
views
Computational complexity of fractions multiplication puzzle
I developed a puzzle for which I am seeking an EFFICIENT algorithm (I searched Google but did not find this puzzle in the literature, ):
You have $k$ rationals, $n_1/d_1, n_2/d_2, ..., n_k/d_k$.
...
- 2,993
1
vote
0
answers
36
views
Is there an algorithm for this constrained Hypergraph optimization problem?
I'm currently developing an algorithm for computing knot coloring invariants and got to the following question:
Given a set $S$ and a certain hyper-graph $H \subseteq S^3 $, find a decomposition $S = ...
- 133
1
vote
0
answers
29
views
Existence of Costas array with specified displacment vectors?
Costas array is a set of $n$ points lying on the square of a $n×n$ checkerboard, such that each row or column contains only one point, and that all of the $n(n − 1)/2$ displacement vectors between ...
- 2,993