All Questions
1,809 questions
1
vote
1
answer
219
views
approximate diameter of polytopes in high dimensions
I just came across the following problem:
Let us consider the unit corner of the n-cube
$$
\Delta^n = \left\{(t_1,\cdots,t_n)\in\mathbb{R}^n\mid\sum_{i = 1}^{n}{t_i} \leq 1 \mbox{ and } t_i \ge 0 \...
- 75
1
vote
0
answers
171
views
Finding all feasible solutions
Let $u$ be a $n_{max} \times m$ matrix. Let $z$ be a $n_{max} \times s_{max} \times n_{max}$ cube. Let $w$ be a $n_{max} \times 1$ vector. All the three matrices can have values from the set $\{ 0, 1\}...
- 175
1
vote
0
answers
120
views
The column generation technique on a Train Unit Assignment Problem [Linear Programming]
I am doing an assignment where I need to implement a mathematical model that I can't wrap my head around. For the technique of column generation, one would need to my understanding, a master problem ...
- 111
1
vote
0
answers
112
views
Canonical representation of binary decision trees in Ptime?
I am wondering about the possibility of efficiently (here: in Ptime) representing binary decision trees (BDT) by some other data structure in a way that characterizes their equivalence.
More ...
- 111
1
vote
0
answers
172
views
Is there a polynomial time algorithm for Poly-trees (Oriented trees) isomorphism?
In terms of graph isomorphism complexity classes Trees have a polynomial time algorithm and Directed Acyclic Graphs (DAG's) do not (so far).
What about Poly-trees (oriented trees)? These are DAG's ...
1
vote
0
answers
85
views
Smallest sum of original column entries in 2d matrix [closed]
I have an interesting optimization problem I am trying to solve now and I thought I'd share it here in order to find the best answer. The problem itself is not complicated and it is stated like this:
...
- 111
1
vote
0
answers
132
views
Complexity :: Integer Programming :: Non-Poly Example [closed]
When learning about computational complexity I find that when discussing the NP-Complete problems authors always give examples of such problems that can in fact be solved in poly time.
I understand ...
- 19
1
vote
0
answers
138
views
FPTAS for approximating the permanent of a matrix
My question concerns approximating permanent of an $n$-by-$n$ matrix.
Several approximation algorithms have been proposed in the literature for this purpose, whose time complexity depend on $n$ and ...
- 11
1
vote
0
answers
164
views
What's the complexity of the one sink directed subgraph isomorphism problem?
I am considering trying a new approach for the subgraph isomorphism problem in my PhD, but it just seems to work well for digraphs of one sink. By working well I mean some promise of not having to ...
1
vote
0
answers
128
views
Reducing enumeration of reduced words in general Coxeter groups to another #P-complete problem
There is a polynomial time algorithm that takes as inputs a Coxeter system $(W,S)$ with $S$ finite (but with $W$ not necessarily finite), say encoded as a Coxeter matrix, as well as two reduced words ...
- 2,168
1
vote
1
answer
100
views
Is it known whether Minimum Cost Multicut is APX-hard?
My questions is concerned with the following problem: Given an undirected graph $G = (V, E)$ and (edge costs) $c \in \mathbb{Z}^E$,
$$\min \left\{ \sum_{e \in E} c_e x_e\ \middle|\ x \in \{0,1\}^E \ \...
- 119
1
vote
0
answers
82
views
Recognizing bridgeless cubic graph with special 2-factor
A 2-factor of graph $G(V, E)$ is a set of vertex-disjoint cycles that cover $V$. It is known that every connected bridgeless cubic graph contains a 2-factor (and a perfect matching).
I conjecture ...
- 2,993
1
vote
1
answer
6k
views
Convert linear programming problem into its standard form [closed]
all,
I met a question that, the cost function of the linear programming problem is a function with absolute value. Here is the problem:
min 3x1+|6x2+3|
st.
|x1+4|+|2x2|<=3
How can I deal with it?...
- 13
1
vote
0
answers
140
views
Reduce a Combinatorial problem
It is given n sets with k vectors. (k is element-wise positive or zero)
Choose one vector of each set so that the biggest element of the sum of the chosen vectors is minimal.
What i also know but is ...
- 11
1
vote
0
answers
68
views
Polynomial problems in graph classes defined by forbidden induced cyclic subgraphs
Let $C$ be a graph class defined by a finite
number of forbidden induced subgraphs, all
of which are cyclic (contain at least one cycle).
Are there graph problems that can be solved in
polynomial ...
- 25.4k
1
vote
0
answers
115
views
What is the generic complexity of First Order Predicate Calculus?
I suspect that it should be the same as that of the Turing machine halting problem, which wikipedia gives as GenP and attributes this result to Hamkins and Miasnikov, but I am not sure. Is the generic ...
- 111
1
vote
2
answers
172
views
Linear Programm with matrix [closed]
Is there a name for problems like this
min norm(Cx)
Ax = b
where C is a matrix and norm is the maximum norm.
This is kind of like a linear Programm. Could this be rewritten as linear programm? Or Any ...
- 11
1
vote
0
answers
74
views
TSP: Approximation Ratio of the Double Tree Heuristic after Diagonals have been Removed
In their article "Double-Tree Approximations for the Metric TSP: Is the Best One Good Enough?", Vladimir Deineko and Alexander Tiskin derive a lower bound for the approximation ratio of the double-...
- 13.2k
1
vote
0
answers
75
views
Are there any known bounds on the value of solutions of linear integer programming?
Given a linear objective function and a system of linear constraints; are there any known bounds on the values of (positive) integral solutions in terms of the coefficient matrix of the constraints?
...
- 111
1
vote
0
answers
493
views
Complexity of Nested Linear Optimization
My question is motivated by the fact, that among other ways, it is possible to restrict a variable to two discrete values, e.g. the prototypical $0$ and $1$, via an optimization constraint:
$$\max(\...
- 13.2k
1
vote
0
answers
702
views
How to prove the NP-hardness of this scheduling problem? [closed]
Suppose there are a set of $m$ jobs $J= \{J_1, J_2, \ldots, J_m\}$ and $n$ machines $M=\{M_1, M_2, \ldots, M_n\}$. Each job $J_i$ consists of $k_i$ unit operations, and there are totally K operations $...
- 23
1
vote
0
answers
157
views
Indecomposability of image transformations (pure algebra). Open questions
W-transformations -- definitions
We will consider a class called finite window transformations $\ T:C^\mathbb Z\rightarrow C^\mathbb Z\ $ defined a paragraph below; $\ \mathbb Z\ $ is the ring of ...
- 7,500
1
vote
0
answers
196
views
Interior point optimisation using big M for L1 norm on linear system using Dikin's Affine method
I am a 4th year undergrad surveying student studying computations, specifically $L_{1}$ norm minimisation of residuals in large data sets. To start with (and probably to finish with) I'm using a set ...
- 111
1
vote
0
answers
256
views
Equal maximum and minimum in a large-scale linear programming
For a linear optimization of an integral (with integral constraints), I perform a linear programming for the equivalent series. Maximum and minimum of the LP problem tend to be equal as I increase the ...
- 111
1
vote
0
answers
111
views
Schönhage's SMM with only one instruction
It is possible to implement $\lambda$-calculus in Schönhage's storage modification machine using an infinite set of nodes and one single program consisted exclusively of (about hundred) instructions ...
1
vote
0
answers
145
views
Are set covering problems with nonlinear cost functions NP-Hard?
Are set covering problems (set cover problem wikipedia) with a nonlinear cost function also NP-hard? Is there a general result about this?
To be more specific the cost function I am interested in ...
1
vote
0
answers
1k
views
Robust optimization in matlab using fmincon [closed]
I am trying to implement the following optimization (from this paper) in Matlab using fmincon:
$\min_\omega\omega'\Sigma\omega$ subject to $\min_Ur_p \geq r_0$
where $\Sigma$ is a positive definite ...
1
vote
0
answers
145
views
NP problem implications [closed]
Hi, i would like to have some clarification on NP-completeness.
In particular I'm reading an article where they show:
1) Partitioning the edges of a graph into connected component of 3 edges (3-path ...
- 11
1
vote
0
answers
126
views
Matrix Minimax problem
I have the equation $\Sigma_k(M_k{p_k})V=EV$, where the $M_k$ are n*n real Hermitian matrices, $V$ is a n*n eigenvector matrix, $E$ a dim-n energy eigenvector and the $p_k$ scalar parameters. The $M_k$...
- 4,829
1
vote
0
answers
112
views
Did anybody come across a computational problem which is related to the notion of cartesian product and is at least NP-hard?
Did anybody come across a computational problem which is related to the notion of cartesian product and is at least NP-hard?
Equally interesting would be to learn about such problems with a non-...
- 41
1
vote
0
answers
89
views
Deciding / Approximating Parity of Small Depth Decision Trees
Let C be a circuit such that:
C: $\{0,1\}^n$ to $\{0,1\}$
the top most gate is a parity gate
all the inputs to the parity gate are small depth decision trees
there is a total of $2^{ log^k n}$ ...
- 45
1
vote
0
answers
628
views
Totally unimodular Matrices
A matrix is totally uni-modular if the determinant of any (square) sub-matrix is {+1, 0, -1}. My question is, "Is there a way to transform(linear or non) a general matrix into a totally uni-modular ...
- 11
1
vote
1
answer
241
views
Covering max flow arcs by arc disjoint paths
Let $(N,A,s,t,u)$ be a network with node set $N$, arc set $A$, source $s\in N$, sink $t\in N$ and capacity vector $u\in\{1,2,\ldots,T\}^A$, and let $x=(x_a)_{a\in A}$ be a maximum $(s,t)$-flow. Is it ...
- 2,966
1
vote
0
answers
266
views
Multiobjective semidefinite programming
Let $C$ be size $n \times n^{2}$.
Let $B$ be size $2^{g(n)} \times n^{2}$ where $g(n) > n$.
There is only one $\mathcal{1}$ per row of $C$ and remaining entries of $C$ are $\mathcal{0}$.
$B$ is ...
- 800
1
vote
0
answers
1k
views
How to solve simple bilinear equations under extra linear constraints
Hello,
This is the full version of a question I asked earlier. I am trying to understand whether finding a solution to the following bilinear system is computationally hard or easy:
$\lambda_i^T u_{...
- 53
1
vote
0
answers
538
views
Representing vertices of a cube using linear combination of tensor product of smaller cubes
Let $n,N \in \mathbb{N}$ with $N \ge n^{2}$.
Let $F[i] = \square[i]$ refer to the cube which has vertices from $\{-1,0,1\}^{n^{i}}$ ($n^{i}$ tuple of alphabets from $\{-1,0,1\} = \square[0] = F[0]$)
...
1
vote
0
answers
228
views
Inherent complexity of a language --- when does it exist?
For a language $L$, you can talk about the complexity of a Turing machine $M$ which decides $L$. Can you talk about the time complexity of the language $L$ itself, i.e. say $L$ has complexity $f(n)$ ...
- 3,475
1
vote
0
answers
117
views
Formal Definition of Random Reducibility
What is the formal definition of Random Reducibility>
Arora/Barak is like:
"yeah, so it's kind like you take an instance of a problem, create n random instances of the problem; and if you have the ...
- 11
1
vote
0
answers
357
views
Is this minimization problem NP-Complete ?
We are given an $n\times (n+k)$ matrix $A,$ with entries in $\mathrm{GF}(2),$ of the form $A=(I_n|B)$ where $I_n$ is a $n\times n$ identity matrix where the matrix $B$ has no "zero" rows or columns.
...
- 209
1
vote
1
answer
1k
views
Knapsack Problem Specifics [closed]
(i) Are there limits on how many numbers must be in the set? { 1, 2 } or { 1, 5, 7, 8 , 9}
(ii) Are there limitations on how diverse or similar the numbers in the set can be? Coprime? Pairwise? { 1, ...
- 13
1
vote
0
answers
376
views
NP-complete variants of NPI problems
Motivated by these posts, An NP-complete variant of factoring and Relationship between symmetry and computational intractability, It seems to be worthwhile to investigate the different factors that ...
- 2,993
1
vote
0
answers
638
views
Expected value of sum of fractions
Suppose $r$ is a set of attributes with probabilities while $p$ is a set of attributes without probabilities. For example, say that $r$ = {$a$:0.4, $b$:1.0} and $p$ = {$a$, $c$}. (Here, $a.prob = 0.4$ ...
- 21
1
vote
0
answers
282
views
Complexity of a problem related to 3D matching?
Given a set of triples of a base set $S$, find a subset of triples such that each element in $S$ appears exactly in one triple. This problem is NP-complete by reduction from NP-complete problem 3D ...
- 2,993
1
vote
1
answer
2k
views
Proving APSPACE = EXP [closed]
AP = Alternating Polynomial Time
PSPACE = Polynomial Space
APSPACE = Alternating Polynomial Space
EXP = Exponential time
Proving AP = PSPACE is fairly easy:
1) TQBF is PSPACE complete
2) AP can ...
- 663
1
vote
0
answers
259
views
Self-improvement property of optimazation problems?
Maximum CLIQUE problem is very hard to approximate. It has a self-improvement property defined using graph product which is utilized to prove hardness of approximation results. One such example is ...
- 2,993
1
vote
0
answers
576
views
Minimizing quadratic form over permutations
Let $Q$ be an $n \times n$ real symmetric matrix and $x$ an $n \times 1$ real vector. Consider the following minimization problem:
$\min_{\pi \in S_n} ~(\pi x)^{\rm T} Q (\pi x)$,
where $S_n$ ...
- 1,839
1
vote
0
answers
1k
views
Covariance matrix formula interpretation - what am I missing?
I'm reading a paper that outlines the calculation of a covariance matrix like the following:
$C=\displaystyle\sum^{N_b}_{i=1}\vec{x}_i\vec{x}_i^T$
What is the order of this matrix? My interpretation ...
- 111
0
votes
1
answer
1k
views
For Ax = b, x and b unknown vectors, how do I solve the x that maximizes min(b_i)?
Given a matrix $A$, each element $A_{i,j} \geq 0$, find the vector $\vec x$ that maximizes the minimum element in $\vec b$ ($\vec b = A \vec x$). Note that this is not a linear equation system as I ...
- 135
0
votes
1
answer
875
views
Counterexample to Pólya's conjecture
It is known that Polya's conjecture is false and the smallest counter-example is about $10^9$.
Assuming that we are searching for a counter-example not knowing that it exists. What useful information ...
- 111
0
votes
1
answer
257
views
Non-uniform constant-depth circuits
Non-uniform circuits, according to my understanding, are those which have different circuit depending on the input size. Constant depth circuit are those whose depth is constant in the input size. So ...
- 193