All Questions
1,809 questions
1
vote
0
answers
70
views
Shortest Lattice Vector with restricted $x$
Let $\Lambda$ be a lattice with basis, $B$ consisting of vectors $b_i$, so that the elements of $\Lambda$ are of form, $y\in \Lambda \iff y=Bx=\sum_i b_ix_i$ for some $x_i\in\mathbb{Z}$.
My questions ...
- 1,096
1
vote
0
answers
207
views
Is it known whether $\mathrm{NP \subseteq P/poly}$?
It is not immediately clear to me whether this statement is true or false. Can finite restrictions of NP problems be computed in polynomial time?
- 11
1
vote
1
answer
182
views
How many iterations the best biprime factoring method has to factor a number [closed]
I'm researching method of biprime number factoring. I have a biprime number 1012322327 * 1115382761 (19 decimal digits= 1129126872111204847). I'd like to know how many iterations (or trials) the best ...
- 113
1
vote
0
answers
74
views
How to minimize n-polytope's bounding box with linear transformation?
I am working on an exact algorithm for integer linear programming for my master's thesis:
$Ax\leq b, x \in \mathbb{Z}^n$
$cx\rightarrow min$
For my idea to work out, I need a guarantee that n-...
- 11
1
vote
0
answers
85
views
"Barrier functions" in function spaces [closed]
In general the idea of a "barrier function" (as in the context of "interior point methods") can possibly be thought of as defining a function corresponding to an open subset of $\mathbb{R}^n$ such ...
- 2,246
1
vote
0
answers
103
views
descriptive complexity theory to attack computational complexity problems [closed]
What is the usefulness of descriptive complexity to attack computational complexity theory?what are the recent results in this direction? Thanks
- 11
1
vote
0
answers
78
views
Bipartite clustering is NP-hard?
Let $G = (A\cup B, E)$ be a bipartite graph with edge weights $w: E\to \mathbb{R}$. Find a partition $B_1, B_2$ of $B$ and a nonempty disjoint subsets $A_1, A_2$ of $A$ such that $w(A_1,B_1) + w(A_2, ...
- 221
1
vote
0
answers
140
views
Is the partition of bipartite graphs NP-hard?
I wonder if the following problem is NP-hard. Is it?
Given a bipartite graph $G = (U, V, E)$ with weights $w : E \to \mathbb{R}_+$, find a partition of $U$ into $U_1, U_2$ and nonempty disjoint ...
- 221
1
vote
0
answers
66
views
On number of solutions by simplex and number of solutions in total in a linear optimization problem?
This is more of a clarification query.
Mizuno http://www2.ims.nus.edu.sg/Programs/012opti/files/talk_mizuno1.pdf says if we give a linear optimization problem
$$\max c'x$$
$$Ax\leq b$$
where $A\in\...
- 13.9k
1
vote
0
answers
62
views
LP Constraints for Bridgeless Cactus Graphs
When trying to determine the optimal bridgeless spanning cactus graph of a weighted, symmetric graph, I got stuck.
What I do not know how to capture, is
the variable number and sizes of the cycles
...
- 13.2k
1
vote
0
answers
60
views
On the defect of a flow network
This problem in graph theory was actually motivated by some problems in Theory of Fractals.
To formulate the problem I need to recall some definitions related to flow network.
A flow network is a ...
- 41.8k
1
vote
0
answers
86
views
Infinite system of equations with finitely many constraints
During my research I have stumbled upon the following issue concerning infinite systems of linear equations. I do not have much practice in such settings, so I am asking you whether the following ...
- 1,151
1
vote
0
answers
246
views
How to solve a large linear programming problem? [closed]
I have the linear programming problem in $\mathbf x \in\mathbb R^n$
$$\begin{array}{ll} \text{minimize} & \mathbf c^T\mathbf x\\ \text{subject to} & \mathbf A\mathbf x \leq \mathbf b\end{...
- 149
1
vote
0
answers
44
views
In convex optimization we know that the optimum solution is on which hyper plane
We have a standard linear program, I mean a set of inequalities $c_i^Tx\leq b_i$ where $i\in \{1,\ldots ,k\}$ and we want to find $max\{c^Ty| y\in \{\cap \{x|c_i^Tx\leq b_i\}\}$. I put some condition ...
- 19
1
vote
0
answers
384
views
Complexity of conic optimization problems
I am interested in bounding the computational complexity of the interior points method for solving a generic conic problem of the form
\begin{equation}
\min_x \left\{ c^T x : \mathcal{A}x-B\in\mathbf{...
- 345
1
vote
0
answers
87
views
computing number of primes with congruence constraint
Suppose I give you $(a, b, M)$ and ask you to compute the number of primes not exceeding $M$ which are congruent to $b$ mod $a.$ What is the most efficient way of doing it? (without congruence ...
- 96.4k
1
vote
0
answers
105
views
How is the minimax oracle used to find the oracle complexity of projected subgradient?
I am going through a set of blog posts on the complexity of projected gradient method.
https://blogs.princeton.edu/imabandit/2013/03/15/orf523-oracle-complexity-large-scale-optimization/ defines the ...
- 277
1
vote
0
answers
261
views
Prove that the following set of triples forms a convex polytope
Take $a,\,b,\,c,\,d \in \mathbb R_+$ such that $a+b+c+d=1$. Define:
\begin{equation}
x_1 = \min(a+b,\,c+d)\,,\qquad x_2 = \min(a+c,\,b+d)\,,\qquad x_3 = \min(a+d,\,b+c)\;.
\end{equation}
I would like ...
- 31
1
vote
0
answers
49
views
Cost associated set problem NP-hard
I have the following problem. I wonder whether or not it appears in the literature. Is it NP-hard?
Given a set $S = \{1,2,\ldots,m\}$, and $A_1,\ldots, A_n$ are subsets of $S$. Each set $A_i$ has ...
- 221
1
vote
0
answers
102
views
Is a problem that is NP-hard to solve under known future still NP-hard to solve under random future? [closed]
The problem comes from network coding area. There is a wireless server that holds a set of data packets. There is a set of receivers, each already possesses a subset of the data packets, and wants all ...
- 19
1
vote
0
answers
42
views
Computation of sub-gradient for a concave envelope
Let $x_1<\cdots<x_n$ be $n$ points on real line and $g=(g_1,\cdots, g_n)\in\mathbb R^n$ be the scattered data. Let $u_g: [x_1,x_n]\to\mathbb R$ be the linear interpolation of $g_1,\cdots, g_n$, ...
- 345
1
vote
0
answers
81
views
Maximizing sum of homogeneous functions of order one over a polytope
Let $f_i: \mathbb{R}^n\rightarrow \mathbb{R}$ be
concave, increasing (i.e., if $x\geq y$ where the inequality is entry wise, we have $f_i(x)\geq f_i(y)$), and a
homogeneous function of order one for ...
- 393
1
vote
0
answers
88
views
On convex quadratic programming clarification
We know convex quadratic programming is in $P$.
Is it also in $P$ if the function of interest is only convex in the domain of interest?
- 13.9k
1
vote
0
answers
20
views
Calculating Cost-Optimal 1-Factors in Digraphs
I need to find a cost-optimal 1-factor in a positively weighted, directed, regular graph $G(V,A)$ without antiparallel arcs, i.e. given $$\text{deg}_{\text{in}}(u)=\text{deg}_{\text{in}}(v)=\text{deg}...
- 13.2k
1
vote
0
answers
78
views
Family of functions which satisfies $f(\boldsymbol{x}) = 0$ if $\nabla f(\boldsymbol{x})=0$? [closed]
I have a Lagrangian of which I want to find the supremum in the primal variable $\boldsymbol{x}$:
$\mathscr{L}(\boldsymbol{x},\boldsymbol{\lambda})=f(\boldsymbol{x})^T\boldsymbol{a} + \boldsymbol{\...
1
vote
0
answers
47
views
Linear programs [closed]
Can the optimal value of the primal problem of a linear program ever be less then zero?
An example is: minimize $C=2x_1 +3x_2$ Subject to: $3x_1+4x_2 \leq 5$. Obviously, $x_1$ and $x_2$ are free ...
- 11
1
vote
0
answers
93
views
quick hull algorithm detail
When using quick hull algorithm to find the polytope for half space intersection, we are required to provide an interior point to the solver qhalf.
In other words, providing
$$Ax \le b$$
is not ...
- 867
1
vote
0
answers
43
views
a question about probabilities on spaces of digraphs
Let $G$ be a directed graph with fixed nodes $s$ and $t$. Assume that each edge $e$ in the graph comes with a number $n(e)\in[0,1]$.
We consider probability spaces $S$ whose points are directed ...
- 61
1
vote
1
answer
73
views
minimize number of unique elements in a vector
I was wondering if there is a simple or known way to minimize the number of unique elements in a decision variable (vector). Note that I'm not asking for minimization of nonzero elements (rank ...
- 13
1
vote
0
answers
153
views
NP-Hardness of Underdetermined Systems over $F_2$ implies the same for $F_{p^q}$
Assume that the yes-no problem of whether $x' \in F_{p^q}^{n}$ is a minimal support solution for a consistent underdetermined system $Ax=b,$ $A \in F_{p^q}^{m \times n}, b \in F_{p^q}^n$ is an NP-hard ...
- 259
1
vote
0
answers
673
views
Why are SDP generally slow?
This is more of a conceptual question. Don't expect a highly mathematical question. Nonetheless, the questions I pose here often arise in my field (not mathematics).
Usually Semidefinite Programs (...
- 345
1
vote
0
answers
1k
views
Number of different combinations in a 0-1 knapsack problem with integer weights [closed]
My question is actually very similar to this other one: Given a vector of positive integers, count the number of combinations which have a sum that produces a different value. But, since this previous ...
- 153
1
vote
0
answers
1k
views
Analytic formula for minimizing the maximum inner product of a set of vectors
Given $x_j\in\mathbb{R}^n$, $j=1,\ldots,p$, find
$$
\widehat{w} \in \arg\min_{\Vert w\Vert=1}\max_{1\le j\le p} |\langle w,x_j\rangle|.
$$
I am also interested in the special case where we further ...
- 710
1
vote
0
answers
73
views
Is there any notion of a slack-matrix (and its rank) for a hyperplane arrangement?
I am assuming that the common lineality space of the hyperplane arrangement has already been factored out. So we are looking at an ``effective" arrangement in lower dimensions where all the polyhedra ...
- 2,246
1
vote
0
answers
107
views
Effective estimates for circle packing
The Riemann map from a simply connected domain to the unit disc can be approximated by circle packings thanks to a theorem of Rodin and Sullivan. (That is, take smaller and smaller triangulations and ...
- 3,383
1
vote
0
answers
187
views
Strong Duality of Mixed Integer Linear Program
The problem at hand is to optimize a mixed-integer linear program closely related to the maximum flow problem. I would like to reformulate the problem with its dual and I'm concerned with the ...
- 11
1
vote
0
answers
152
views
Efficient deterministic algorithms of factorizing
My question is about efficient deterministic algorithms of factorizing polynomials of degree $n$ over $\mathbb{F}_q$.
Are there such algorithms that use poly$(n, \log q)$ bit operations?
I know ...
- 2,576
1
vote
0
answers
64
views
Maximize discrete harmonic function at given point
Let $n>0$, and let $S_n$ denote the discrete square
$S_n=[|-n,n|]^2$ (so $S_n$ has $(2n+1)^2$ elements). Let $K_n$ denote the set of four corner points $\lbrace (\pm n,\pm n)\rbrace$, and $C_n=S_n\...
- 621
1
vote
0
answers
55
views
Separation on discrete set
Consider the set $L = \prod_{i=1}^n\{1,0\}$, i.e. L consists of the element of n-tuples whose entries are 0 or 1. Also we can regard $L$ as a subset of $R^n$.
Define linear functions $f(x)= a_1x_1+ \...
- 61
1
vote
0
answers
129
views
Analogues of Specker sequences for different complexity classes
Consider the standard definition of computable real numbers: a real number $r$ is computable just in case $r$ is the limit of a sequence $(a_i)_{i \in \mathbb{N}}$ such that (1) the function $i \...
- 1,155
1
vote
0
answers
139
views
bounded degree graph colouring.
I was wondering if anyone could provide references on the following:
Is determining the chromatic number of a bounded degree graph APX-complete?
2.I've seen the result that states it is NP-hard to ...
- 903
1
vote
0
answers
90
views
Calculation of cardinality of Jacobians
The problem of calculation the number of rational points on curves over finite fields is $\#P$-complete - "Counting curves and their projections".
Is it true for calculation of number of rational ...
- 2,576
1
vote
0
answers
43
views
Reference requests for tiling easiness [closed]
For Wang tile problem, is there some general statements in a paper stating that the more tiles (supposed provided by random) available, the easier it is for these tiles to tile the plane? Thank you.
- 867
1
vote
0
answers
167
views
How I can prove the equality $P^{P_{\operatorname{space}}}=NP^{P_{\operatorname{space}}}=P_{\operatorname{space}}^{P_{\operatorname{space}}}$ [closed]
I know how to prove that if $A \in P^{P_{\operatorname{space}}}$ then $A \in NP^{P_{\operatorname{space}}}$ and $A \in P_{\operatorname{space}}^{P_{\operatorname{space}}}$.
I don't know how to prove ...
- 119
1
vote
0
answers
28
views
The complexity of Max-K interval selection
I came up with the following problem, but do not know how to analyze it.
Let $S$ be an ordered set of integers with size $n$ (i.e., $S=\{1,2,...,n\}$). An interval $INV(a,b)$ covers the elements in $...
- 11
1
vote
0
answers
34
views
Some confusion regarding the definition of NPO reduction
I've seen the following definition in a paper on approximation preserving reductions.
Definition:Let $\pi_{1}$ and $\pi_{2}$ be two NPO maximization problems. Then we say that $\pi_{1} \leq_{R} \pi_{...
- 213
1
vote
0
answers
144
views
On variant of integer factorization
In the post on site cstheory.stackexchange on whether a variant of integer factorization
$$\mathsf{}\mbox{ }{\Pi} = \{\langle a, b, n \rangle \;|\; \exists \mbox{ } \mathsf{ an}\mbox{ }\mathsf{ ...
- 13.9k
1
vote
0
answers
203
views
A reference for "Borel Sets and Circuit Complexity"
Is there any pdf version of M.Sipser's "Borel Sets and Circuit Complexity" or , since I am unable to get this paper, is there other reference closely related to theory in that paper?
- 51
1
vote
0
answers
41
views
Complexity of finding algebraic dependency of polynomials over the rationals or in a finite field?
Let $f_1,\ldots f_m \in K[x_1,\ldots,x_n]$ where $K$ is $\mathbb{Q}$ or a finite field.
Q1 What is the complexity of finding all algebraic dependencies between $f_i$?
Q2 What is the complexity of ...
- 25.4k
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