All Questions
Tagged with computational-complexity optimization
89
questions
3votes
3answers
138views
Can we somehow compute $(z^2 - 1)(z^2 - 4)(z^2 - 9)(z^2 - 16) \cdots (z^2 - k^2)$ in half the number of operations?
Let $f(z, k) = (z^2 - 1)(z^2 - 2^2)(z^2 - 3^2)(z^2 - 4^2) \cdots (z^2 - k^2)$ in less than $1 + k + k + k + (k-1) = 4k$ arithmetic operations, specifically I need it to be roughly $2k$ operations or ...
- 19.3k
0votes
0answers
14views
VRP: Relative performance savings algorithm of Clarke and Wright for equal distance
I'am getting stuck at the following problem.
Consider a vehicle routing problem (VRP) with one depot and
2n vehicles. Each vehicle has capacity Q. There are n customers with
demand q1, . . . , qn (qi ≤...
0votes
0answers
94views
Simplify this 7 vertices 4-Clique Boolean algebra
Simplify the Boolean algebra below. There is no "Not" operation in the Boolean algebra. haha
Relevant Definition:
This is a Clique problem, trying to find 4 vertices clique in 7 vertices ...
0votes
1answer
27views
What is approximation ratio?
I am looking at the wikipedia page of TSP. I am confused by this statement.
"If the distance measure is a metric (and thus symmetric), the problem becomes APX-complete and the algorithm of ...
- 1
6votes
1answer
105views
Reasoning behind choosing appropriate decomposition when solving linear equation.
Now I am reading the book "Introduction to linear algebra" by Gilbert Strang. I understand all the technical details regarding LU, QR and SVD decompositions, but I get completely confused ...
- 860
0votes
0answers
72views
NP completeness of a variant of assignment problem
I have the following variant of assignment problem:
Suppose we have $m$ machines and $n$ jobs. Each machine is capable of doing a subset of jobs and each machine $i$ has capacity $C_i$. Each job $j$ ...
- 402
2votes
1answer
39views
Minimum Vertex Cover of 2 vertex disjoint but connected odd cycles.
Consider the graph G, which is comprised of 2 vertex disjoint odd cycles (C1, C2) where |C1| & |C2| >= 5. G is sub-cubic and connected, with edges in between the cycles. Because G is sub-cubic, ...
- 43
0votes
0answers
25views
Complexity of a problem similar to the bounded knapsack problem
I am trying to know the complexity of the following two problems. The two problems are to find the set of integers $n_i$.
Problem 1:
min $$\sum_i n_i V_i$$
s.t. $$\sum_i n_i \le U$$
$$ \sum_i n_i V_i ...
- 89
3votes
0answers
47views
Efficiently finding the minimizer of a quadratic function over a finite subset of $\Bbb R^m$
Given matrix $A \in \Bbb R^{m \times m}$, let function $f : \Bbb R^m \to \Bbb R$ defined by
$$f(x) := x^T A x$$
Suppose there are $n \gg m$ points $a_i \in \Bbb R^m$. I seek to find
$$\min_{i \in [n]} ...
- 124
2votes
0answers
39views
Non optimal multiple traveling salesman problem
The following is a variation of the multiple traveling salesman problem (MTSP) where the salesman begin at different locations:
There are $S$ sites in a city at different fixed geo locations $(a_i,a_i)...
- 15k
1vote
2answers
77views
Simplification of the Traveling Salesman Problem
I'm not sure I can call it a simplification of TSP but here it is:
Suppose you're given the Traveling Salesman Problem but in addition, you're also given the shortest possible distance (not the route) ...
- 61
3votes
0answers
96views
Reducing column ranges of a matrix
I'm looking for an algorithm to reduce the sum of column ranges in a sparse integer matrix by subtracting $1$ from all nonzero elements in a subset of the rows.
Let $R = 1, \ldots, m$ and $C = 1, \...
- 116
1vote
1answer
39views
Maximum of weighted sum of exponentials
Given a function
$$f(t) := \sum_k a_k e^{b_k t} $$
for some $b_k < 0$, we want to find maximum of $f(t)$ over $t > 0$ algorithmically.
A solution would be to calculate $f'(t)$ and and then ...
- 31
1vote
0answers
36views
How can we efficiently optimise $\sum_{i=1}^N \|a_i -x\|_\infty ^2$ for $N$ very large?
Suppose $n$ is very large and we want to minimise the convex function $\sum_{i=1}^n ||a_i -x||_\infty ^2$ over some compact convex $X \subset \mathbb R^d$. The difficulty with attemtpting this ...
- 8,436
2votes
1answer
72views
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*}
...
- 21
1vote
0answers
29views
the centroid-based clustering is NP-hard
I am trying to understand why the centroid-based clustering is NP-hard.
Assume we have one-dimensional sorted data set $x_{1}, \dots, x_{n}$ and we want to find, say $k$, optimal clusters (intervals) $...
- 273
1vote
2answers
80views
Solving QUBO: does the knowledge of the optimal solution help with finding an optimal argument?
Let say I have to solve a large QUBO (quadratic unconstrained binary optimization) problem
$$
\min_{x}{x^\top Qx},
$$
where $x\in\{0,1\}^N$ is a binary variable and $Q\in R^{N\times N}$ encodes the ...
- 13
2votes
0answers
35views
Linear programming with approximate arithmetic
One of the big achievements since the 80s is the solution of linear programs, e.g., by barrier method. For example, to solve
$$\begin{array}{ll} \text{minimize} & c^T x\\ \text{subject to} & ...
- 159
1vote
1answer
41views
Good reference that discusses NP hardness in the context of optimization?
Sometimes I read a book on optimization and the author states (without proof) that finding a certain solution to the (non-convex) optimization problem is NP hard.
I've learned about complexity theory ...
- 743
0votes
0answers
48views
Computational complexity of optimizing the difference between two concave functions
I know the difference of two convex functions is called D.C. Program, see Horst R, Thoai N V. DC programming: overview[J]. Journal of Optimization Theory and Applications, 1999, 103(1): 1-43.
However,...
- 121
1vote
0answers
82views
Complexity of semidefinite programming
From this paper, I read that
Semidefinite programs can be solved in polynomial time to an arbitrary prescribed precision in the bit model using the ellipsoid method
and
Therefore, interior ...
- 578
1vote
1answer
66views
Linear Programming - A brute force approach
I was wondering what the main drawback for using a brute force approach in Linear Programming would be. My idea would be to just iterate over all possible basic solutions, filter out the infeasible ...
- 2,302
0votes
1answer
189views
Convergence Rate and Complexity of Single SGD update for Neural Networks
Setting:
Fix positive integers $m_1,\dots,m_n$ an activation function $\sigma:\mathbb{R}\rightarrow\mathbb{R}$ be $C^1$ with Lipschitz derivative, and let $NN$ denote the set of all feed-forward ...
user683848
1vote
1answer
23views
minimal distance of a vector to an element of a rectangular box
Consider a known rectangular box $\Omega \in \mathbb{R}^d$, and $x \in \mathbb{R}^d$ a vector.
I would like to determine an inexpensive way to compute $y^* \in \Omega$, such that $$y^* = \arg \min_{y \...
- 233
0votes
1answer
84views
Fast computation of the direction of a vector
I need to compute the direction of 2D vectors that are provided as a pair of 16 bit signed integers, and return an integer in range $[0,256)$.
This can be achieved by the expression
$$\frac{128}\pi\...
user65203
2votes
0answers
41views
Computational complexity of convex constrained quadratic problem?
Let's say the convex constrained quadratic problem reads
\begin{align}
\min_{x \in \mathbb{R}^n, \ t \in \mathbb{R}} \ & \ t\\
\text{s.t.} \ & \ x^TA_ix \leq t + b_i \quad \forall i = 1,\...
- 2,415
0votes
0answers
40views
Computing a target number from a set of natural numbers
Given a set of natural numbers $S=\{n_1,n_2,\ldots,n_m\}$ and a target number $n$, the goal is to compute the target number using only elemental operations, namely $+,-,*,/,(,)$ and numbers from $S$. ...
- 1
0votes
1answer
32views
Show Feature vector on 3d mesh
My case is as following:
I'm trying to extract features from mesh (vertices and faces), for example I had obtained zernike moments
...
- 1
0votes
1answer
45views
Social cost minimization in a congestion game
For a congestion game, is a social cost minimization problem NP-hard?
A congestion game is described as follows:
Given a set $E$ of resorces.
$\cdot$ Each agent $i=1,...,k$ has an explicitly ...
2votes
1answer
62views
Can optimization version problem whose decision version is NP-complete be solved in poly-time iff P=NP?
I have proved the decision version of my problem be $\mathcal{NP}$-complete. And I know that if I can solve the optimization version in poly-time, then I can just to compare the obtained minimum (or ...
- 65
-1votes
1answer
339views
Proving the Optimization version of a problem is also NP-hard
It is well-know that $\mathcal{P}$ and $\mathcal{NP}$ are classes of decision problems. I have proved that the decision version of my problem is $\mathcal{NP}$-complete. How to show that the ...
- 65
1vote
1answer
25views
Why the dynamic solution to vertex cover does not prove anything?
The dynamic programming solution implemented here runs in polynomial time, as discussed here on slide 18. My question is, why does this algorithm not hold value? Why cannot it be reduced to all other ...
- 145
3votes
1answer
107views
Is the following problem NP-complete?
Let $G=(V,E)$ be a directed graph and let $p_{ji}$ be the minimum path weight from $j$ to $i$; Then I can obviously save the path weights in a matrix $P$ similar to an edge weight matrix;
Now the ...
user657766
0votes
0answers
16views
Permutative Constraint on Image Approximation
Motivation
I am trying to explore the idea of constraining the approximation of an image represented by an $m$-by-$n$ matrix $A$ by the values on a linearly-spaced interval of $mn$ elements $L$ ...
- 627
0votes
0answers
57views
Compare different optimization techniques.
Usually, the more you know about the function (gradients, Hessians, etc.) and higher order optimization technique is used (Interpolation methods, Quasi-Newton > Newton's method) > the less function ...
- 101
0votes
1answer
91views
Optimizing Polygon Search
I split de world in X random polygons.
polygons on map
Then I am given a coordinate C1, for instance (-21.45, 7.10), and I want to attribute the right polygon to this coordinate.
The first solution ...
- 1
1vote
1answer
244views
Why adding a few rows of constraints can dramatically slow down the running time of MIP optimization?
I am working on a linear mixed-integer programming (MIP) optimization problem. Let's say the constraint can be denoted as $Ax\leq b$, where A is the constraint matrix.
Previously, A has a dimension ...
- 891
1vote
1answer
104views
Finding nth term in a series
You are given a list of sets of numbers (nested) to derive a sequence such that :
Exactly 1 number must be selected from each of the sets
The sequence is arranged in the ascending order of the sum of ...
- 27
1vote
0answers
32views
Lower Bounding a computation problem
I was looking for the computational complexity of the Mutilated Chessboard Problem waiting to find an upper bound in order to know which category of complexity the problem belonged to.
What i found ...
- 939
2votes
1answer
63views
Maximizing Euclidean length of $\pm 1$-combination of given vectors
Suppose we have 3d vectors $v_1, v_2, \dots, v_n$ where typically $n$ is large (100 or so). Then we want to find a sequence of $\pm$ such that $|\pm v_1 \pm v_2 \pm \dots \pm v_n|$ is maximal. Note ...
- 71
0votes
0answers
324views
Find the upper and lower bounds of a coin weighing problem so that they coincide
We are given $N$ coins which are identical to each other with the exception of only 1 fake coin which is slightly heavier. The problem is to find the heaviest coin. We also have a Balance Scale. One ...
- 113
2votes
2answers
566views
Famous convex maximization problems
Which are the most famous problems having an objective of maximizing a nonlinear convex function (or minimizing a concave function)? As far as I know such an objective with respect to linear ...
2votes
1answer
109views
Assigning drivers to buses and routes
We have a set of N chauffeurs, N buses and N routes, and there are some restrictions about which buses can drive each chauffeur, and which buses can be used in each route given in the form of a graph.
...
- 4,478
0votes
0answers
106views
Quadratic knapsack: minimum variance
I am interested in a simple variant of the quadratic knapsack problem.
Let $\{w_1, \ldots, w_n\} \in \{0,1\}$ be $n$ weights and $\{v_1, \ldots, v_n\} \in \mathbb{R}$ be $n$ values. Furthermore, ...
4votes
1answer
135views
How to reduce calculation time for iterative functions that involve squaring a number in every iteration. Working with numbers in millions of digits
Introduction
I have the below function that is iterated a fixed number of times n. The result of the previous is used in the next iteration and so on. Until we have done n iterations
f(x) = x2 - 2
...
- 41
1vote
0answers
30views
Minimized single-string grammar size approximation.
Let $|\Sigma_s| = m$ alphabet and $|s| = n$ be the size of our string. Consider a minimized grammar $g$ expanding to $s$, with start symbol $S \in \Sigma_g$.
Then what's the maximum length $n$ such ...
- 19.3k
9votes
0answers
246views
Optimal Compass and Straightedge Constructions
I was recently looking over some Islamic geometry patterns, and was struck by the complexity of the constructions needed to create seemingly simple patterns. This got me wondering regarding optimal ...
- 31.5k
0votes
1answer
31views
How to (efficiently) compute the solution to the following equation?
\begin{align}\sum_{i=1}^N\min(1, w^{(i)}/\alpha ) = M,\end{align} where $\alpha \in \mathbb{R}^{+}$ is strictly positive, unknown and has to be found, the $w^{(1)}, \dots w^{(N)}$ are positive, known ...
- 283
0votes
1answer
132views
Can this problem be solved in polynomial time?
I'd like to know about the complexity of the problem below. I believe it might not be possible to solve this with a polynomial time algorithm, but I'd be very happy to be proved wrong.
Problem: Given ...
2votes
0answers
400views
Linear Programming with Incrementally added constraints
I'm working on a project which involves minimizing a particular objective function with respect to a set of linear constraints (i.e a Linear programming problem).
The twist is that, at every time ...
- 143