All Questions
1,809 questions
2
votes
1
answer
102
views
Complexity of recognizing equivalent translation surfaces
"A translation surface is a union of polygons with pairs of parallel edges identified by translation, up to cut and paste equivalence."
I take that succinct (and not fully precise) definition from a ...
- 151k
2
votes
1
answer
186
views
How can I find the maximum value of this function?
For given values of $A \in \mathbb{R}^{m \times n}, b \in \mathbb{R}^m$, how can I find the value of:
$$
\max_{x \in [0,1]^n} \|Ax+b \|_1
$$
Or is this problem NP-hard?
- 23
2
votes
1
answer
152
views
Polynomial degree comparison of Nullstellensatz and Positivstellensatz over real algebraic sets
Suppose we have a (finite) system of polynomials $P = \{ p_i \} \subseteq \mathbb{R}[x_1, \ldots, x_n]$. Then it is well known by the Nullstellensatz that either $P$ has a simultaneous zero over $\...
- 539
2
votes
1
answer
107
views
What is Known about Preprocessing for Stabbing Queries?
In a concrete setting, I have the following problem:
given a fixed set of simple objects (e.g. disks or, convex polygons with few vertices), I need to quickly report the objects that are hit (i.e. ...
- 13.2k
2
votes
1
answer
689
views
Why does the LP Formulation of the MST Problem need Topology Constraints?
I am looking for an example that demonstrates the necessity of either subtour-elimination or of connectivity constraints in the LP formulation of the MST
In the internet I only could find the LP ...
- 13.2k
2
votes
3
answers
753
views
Reference Request for Integer factorization with LP/ILP
Have there been attempts to factor integers with Linear Programming?
Searching the internet suggests that for Integer Factorization only Number Theoretic algorithms, like sieves, are taken into ...
- 13.2k
2
votes
1
answer
2k
views
Finding a point farthest away from $k$ points in a polygon
There are $k$ points placed inside a polygon and I am interested in finding a point inside the polygon (not necessarily on its boundary) who's minimum distance to any of the $k$ points is maximized.
...
- 57
2
votes
1
answer
125
views
Any result or conjecture of computaional complexity of formal languange with rational generating function?
As we know that context-free language is in P,any result or conjecture of computaional complexity of formal languange with rational generating function?And more,any result or conjecture of ...
- 3,094
2
votes
3
answers
398
views
Generating a set of integer passwords that can be securely authenticated
First, apologies for the title. This is an odd question, and I couldn't come up with a simple title for it.
My question is as follows.
Given a positive integer $k$, determine a set of properties $S$ ...
- 135
2
votes
1
answer
849
views
Algorithm for satisfiability of inequalities.
I am looking for an algorithm for checking the satisfiability (with natural values) of a set of inequalities made of variables and natural numbers, for example: $u < v, u \leq z, 3 \leq v$.
In ...
- 85
2
votes
2
answers
2k
views
Solving a system of equations/inequalities that have trigonometric functions on the left-hand side
Is there any known (symbolic) method that solves a system of equations/inequalities that have trigonometric functions on the left-hand side of the system?
Ex) Find $x,y,\theta \in \mathbb{R}$ that ...
- 23
2
votes
1
answer
130
views
Are there intuitive/classically algorithmic analogues to Semidefinite programs on networks?
Many network optimization algorithms, including shortest path, push-relabel, augmenting path, etc, actually have an interpretation in terms of linear programming.
A famous application of semidefinite ...
- 2,383
2
votes
1
answer
646
views
No complexity class contains all recursive languages
I want to prove that there does not exist some complexity class that contains all recursive languages.
Any complexity class C is defined by a complexity measure $\Phi$ (according to Blum axioms) and ...
- 31
2
votes
1
answer
201
views
Are the following to problems in RL complexity class? Proof outline?
L={(G,v)|G is an undirected graph containing at least one circle which itself contains vertex v}
R={(G,v)|G is an undirected graph containing at least one circle which itself contains vertex v, and at ...
- 29
2
votes
1
answer
353
views
poly-time algorithm to choose elements of sets
Let $A_1,A_2,\ldots,A_k$ be finite sets. Furthermore, for each $i\in\{1,2,\ldots,k\}$, let $B_i$ be a set whose elements are subsets of $A_i$.
Is there any polynomial-time algorithm that decides ...
- 85
2
votes
1
answer
92
views
NP-hardness of vertex cover for 3-chromatic graphs
Is the vertex cover problem remains NP-hard for 3-chromatic graphs?
I am almost certain it is, but was unable to find a reference.
Thanks.
2
votes
1
answer
175
views
Optimization over permutation
The Problem
This is the problem I am working on: Given a set $X = \{x_1, x_2, \cdots , x_n\}$ in a metric space, find an optimal ordering $\pi : X \rightarrow X$ that maximizes the following objective ...
- 43
2
votes
1
answer
242
views
Is the problem of vertex enumeration from an H-representation of a polytope NP-hard?
According to the Wikipedia page on the issue, the vertex enumeration problem is NP-hard.
However, double description and reverse linear search are algorithms listed to solve the problem. Moreover, ...
- 123
2
votes
1
answer
46
views
Complexity for determining whether a given metric space is hyperconvex?
Suppose I am given a finite metric space as a distance matrix. What is the complexity of determining whether this metric space is hyperconvex?
Definition: A metric space is said to be hyperconvex if ...
2
votes
2
answers
236
views
Is it NP-hard to find the min set of nodes in a graph so that the set of paths joining them cover all the nodes?
Given a directed graph $G=(V,A)$ and given for every pair of nodes $(i,j)$
a valid path $P(i,j)=(v_1=i,...,v_l=j)$ on $G$.
Find a minimum set of nodes $M$ such that $\bigcup_{(i,j)\in M\times M}P(i,j)=...
- 21
2
votes
1
answer
61
views
Counting the number of pair of d-uplets with upper bounded distance
Consider two d-uplets $u = (u_1,...,u_d)$ and $v = (v_1, ..., v_d)$ both living in $\mathbb{N}^d$ with $d$ a positive integer. They both verify $$(*) \sum_{i=1}^d u_i = \sum_{i=1}^d v_i = k$$ with $k$ ...
- 55
2
votes
2
answers
291
views
Optimizing a multilinear function over the vertices of the cube
Suppose I have $n$ Boolean variables $x_1,\dots,x_n$, and an objective function of the form $f(x_1,\dots,x_n) = \sum_{a_1,\dots,a_n}c_{a_1,\dots,a_n} x_1^{a_1} \cdots x_n^{a_n}$ with $(a_1,\dots,a_n) \...
- 19.7k
2
votes
1
answer
372
views
Who called Farkas' fundamental theorem a lemma?
Farkas proved his famous result (which, nowadays, is fundamental in optimization theory) in 1902 and called it Grundsatz der einfachen Ungleichung which may be translated as fundamental theorem of ...
- 16.5k
2
votes
1
answer
211
views
The complexity of expansion ratio (Cheeger constant) of a graph
Let $G=(V(G), E(G))$ be a graph on $n$ vertices and let $S$ be a subset of $V(G)$. The boundary of $S$, denoted by $\partial S$, is the set of edges $(i, j)$ such that $i \in S$ and $j \in V(G) \...
- 640
2
votes
1
answer
766
views
Integer solution of optimal transport
Let us consider two vectors $\mathbf{a}=(a_1,...,a_n)$ and $\mathbf{b}=(b_1,...,b_m)$ so that each quantity is an integer $a_i,b_j \in \mathbb{N}$. It represents for example supply and demand. Let $\...
- 407
2
votes
1
answer
593
views
Intersection of a vector subspace with a cone
Given a set of vectors $S=\{v_1, v_2,...,v_d\} \subset \mathbb{R}^{N}, \, N>d$, is there any algorithm to decide if there exist a vector with all coordinates strictly positive in the generating ...
2
votes
1
answer
120
views
Can quantum codes have more than $c \cdot \sqrt{N}$ correction distance for N encoding qbits?
I'm not an expert in quantum computing at all, but recently I've started to learn it (read Shen-Vyalyi-Kitaev's book and looked up some other literature here and there).
There are few remarkable ...
- 1,842
2
votes
1
answer
140
views
Matrix completion problem with determinant condition?
Given two $\{0,1\}^{n\times n}$ matrices $L$ and $M$ and an integer $m$ is there a polynomial in $n$ algorithm to find a $\{-1,0,+1\}$ matrix $T$ such that $$\mathsf{det}(L+T\odot M)=m$$ where $\odot$ ...
- 13.9k
2
votes
1
answer
504
views
Feasibility Mixed integer Linear programming with quadratic constraints?
Consider the mixed integer program
$$Ax\leq b$$
$$By\leq c$$
$$\begin{bmatrix}x&y\end{bmatrix}C\begin{bmatrix}x\\y\end{bmatrix}+D\begin{bmatrix}x\\y\end{bmatrix}\leq d$$ where $x$ are integer ...
- 13.9k
2
votes
1
answer
69
views
Clarification on FPTAS optimization in a paper
In the abstract of this paper by Hildebrand, Weismantel & Zemmer it is stated that they provide an FPTAS for $$\min x'Qx$$ over a fixed dimension polyhedron when $Q$ has at most one negative or ...
- 13.9k
2
votes
1
answer
286
views
Memory usage of Gröbner basis computation
I've been calculating some Gröbner bases in preparation for finding non-commutative Hilbert series (and, once I recreate that, characters of group actions). Specifically, I've been using the ...
2
votes
3
answers
462
views
A faster way to spoil an injection?
Ultimately this is about how primes jump. I will abstract the situation somewhat as there may be related applications which do not spring to my mind.
I want to find small spoilers to Hall's Marriage ...
- 13k
2
votes
1
answer
111
views
NP-Hardness of finding minimal-support solutions of underdetermined systems over any field
Given a field $\mathbb{F}$ and a consistent underdetermined system $Ax=b$ over $\mathbb{F},$ $A\in \mathbb{F}^{m \times N}$ and $b \in \mathbb{F}^m,$ finding a vector $z \in \mathbb{F}^N$ such that $...
- 259
2
votes
1
answer
2k
views
3-Approximation Algorithm for 3-Hitting Set
I need to find a $3$-approximation algorithm for finding a $3$-hitting set.
The set-up is that I have a set $S$ and a family $\mathcal{F}$ of subsets of $S$, where each member of $\mathcal{F}$ ...
- 133
2
votes
2
answers
3k
views
Linear programming with infinitely many constraints
I wish to study the following linear program
$$\begin{array}{ll} \text{minimize} & \mathrm c^{\top} \mathrm x\\ \text{subject to} & \mathrm A \mathrm x = \mathrm b\\ & \mathrm x \geq 0\...
- 283
2
votes
1
answer
1k
views
Complementary slackness for approximately optimal Dual solution
Given a Primal LP (P) and it Dual LP (D) we know that the optimal solutions to P ($x_{opt}$) and D $(y_{opt})$ satisfy complementary slackness condition, i.e. under optimal solutions either a ...
- 133
2
votes
1
answer
295
views
Efficiently lifting $a^2+b^2 \equiv c^2 \pmod{n}$ to coprime integers
Let $n$ be integer with unknown factorization. Assume factoring $n$
is inefficient.
Let $a,b,c$ satisfy $a^2+b^2 \equiv c^2 \bmod{n}, 0 \le a,b,c \le n-1$.
Is it possibly to lift the above
...
- 25.4k
2
votes
1
answer
201
views
Minimum cover for sets in which each element appears in exactly 2 sets?
Is there an algorithm for finding minimal covers of a set of sets in which each element of the universe appears in exactly 2 sets? I realize that LP relaxation approximates this to within a factor of ...
2
votes
1
answer
531
views
Complexity of Deciding Feasibility of a system of linear inequalities over restricted variables
I am working out an interesting problem and would like some help with this particular sub problem:
Suppose we have a matrix $ M =\left\lbrace a_{ij}\right\rbrace $ of size $n\times m$ where $ a_{ij}\...
- 21
2
votes
1
answer
3k
views
Complexity of sparse matrix-vector multiplication?
I have a vector $\mathbf{x}$ of size $m\cdot n$ of zeros and ones, i.e., $\mathbf{x}\in\{0,1\}^{m\cdot n}$ and a matrix $\mathbf{A}$ of size $\left(m\cdot n+m+n+1\right)\times\left(m\cdot n\right)$ of ...
- 123
2
votes
1
answer
276
views
An optimization problem in complex space
Consider the following optimization problem
$$
\min \| \textbf{Ax-B}\|
$$
$$
s.t.|x_i|=1,i=1,...,n
$$
where $\textbf{x}\in \mathbb{C}^{n}$ is the optimization varaible, $x_i$ is the $i$-th ...
- 21
2
votes
1
answer
320
views
NP hard problems on UD graphs
I'm reading up on NP hard problems in Unit Disk graphs. I'd like to point out i'm fairly new to this NP hard stuff so i'm trying to get around how to prove something is NP hard.
http://ac.els-cdn....
- 903
2
votes
2
answers
125
views
Deciding whether a given graph has an f-factor or not!
Given a graph $G$ with $n$ vertices and a function $f$ from $\{1,2,...,n\}$ to non-negative integers, Does there exist an efficient (for example polynomial time) algorithm, that decides whether $G$ ...
- 628
2
votes
2
answers
202
views
Combinatorial optimization problem involving infinite spin system
In material science research, I am developing an algorithm to solve an infinite combinatorial optimization problem which I believe is the most natural problem when the system size goes to infinity.
...
- 867
2
votes
1
answer
115
views
enumeration of connected blocks in finite size square
Given a square of size n by m, how many ways could we choose sites, such that all the sites are connected?
By "connected" we mean "connected" by adjacent sites. We will illustrate by example, say, we ...
- 867
2
votes
1
answer
143
views
Find base of kernel with as many 0 as possible
I have a 400x132 rectangular matrix with only 0 and 1.
I am looking for the linear combinations of the columns of the matrix that sum to 0.
For example C1 + C2 - C3 = 0.
I want to find the linear ...
- 83
2
votes
1
answer
191
views
Optimization problem whose cardinality never exceeds 7 for some reason
I am working on a problem in which I have a collection of $n$ points, $x_1,\dots,x_n$, in the plane, as well as a positive definite matrix $\Sigma$ and another point $\mu$ in the plane. I am trying ...
2
votes
1
answer
978
views
Is undirected short-simple-path-through-3-vertices decidable in polynomial time?
Consider the following language:
$L=\{\langle G=(V,E),s,v,t,l\rangle\;|\;s,v,t\in V, l\in \mathbb{N} \wedge $ There exists a simple path from $s$ to $t$, going through $v$ of length $\leq l\}$.
($G$ ...
- 618
2
votes
1
answer
162
views
Complexity of numerically solving systems over the reals
Basically I am interested in
What is the complexity of numerically solving systems over $\mathbb{R}$?
By solving I mean finding at least one numeric solution with given
precision.
Probably the ...
- 25.4k
2
votes
1
answer
227
views
Arrangements of hyperplanes
Fix $n>0$ and $X\subseteq\mathbb{R}^n$. A function $f:X\longrightarrow\mathbb{R}$ is linear if it is of the form
$$
f(\bar{x})=a_1x_1+\ldots+a_nx_n+b
$$
for some $a_i,b\in\mathbb{R}$.
Suppose we ...
- 3,274