0
votes
0answers
37 views

complexity of feasibility checking for a convex optimization problem

I just want to check with you all whether I understand it correctly or not. If I have a convex optimization problem like \begin{align} &\min \quad f(x) \\ & s.t. \quad h(x)≤0, \end{align} and ...
0
votes
1answer
23 views

Are there known patterns among minimal expressions?

Let $R = F[z_1, z_2, \dots]$ be the finite-degree polynomials in a countable number of variables. Let $\mathcal{E}(R)$ be the set of all expressions of polynomials. Note that there could be an ...
2
votes
0answers
31 views

How do you find a minimum of a function with these tools?

Let's say I can define a group $G$ acting on a set of combinatorial objects $X$ and I have a function $f: X \to \Bbb{N}$ that I want to find a minimum of in $X$. Is there a polynomial time ...
3
votes
1answer
111 views

Minimizing Height of a Table

This optimization question popped into my mind while working with latex tables: Suppose we have a table with $m$ rows and $n$ columns, and for each $1\le i\le m,1\le j\le n$ we are given $T(i,j)$ ...
6
votes
1answer
697 views

Why is Dantzig's solution to the knapsack problem only approximate

For a bunch of items with values $v_i$ and weights $w_i$, and with a total weight $W$ that our bag can carry, how do we achieve maximum total value without breaking the bag? Dantzig proposed that we ...
0
votes
3answers
64 views

How to find a set of ascending natural numbers which when added to another set of ascending natural numbers sums to a certain number

Given: $$ X = \left\{ x_1, x_2, \ldots , x_n \right\}\text{ with }x_i \in \mathbb N\text{ and }1 \le x_i \le x_{i+1} $$ $$ z \in \mathbb N $$ Wanted result: $$ Y = \left\{ y_1, y_2, \ldots , y_n ...
2
votes
1answer
66 views

A Matrix Optimization Problem

Given an $n\times d$ matrix $Y$, I am looking for an algorithm to find an $n$-vector $\mathbf{v}$ ($0\le \mathbf{v}_i\le 1$ for all $i$) that minimizes $\sum_{i:X_i<0}X_i$, where $X:= \mathbf{v} ...
0
votes
0answers
22 views

complexity of an optimization problem

Consider $n$ variables $x_1, \cdots, x_n$ with the constraint $\sum_{i=1}^n x_i=1$ and $x_i\geq 0$. I want to minimize $\vec{a}^T (I-\alpha A(\vec{x}))^{-1} \vec{b}$, where $\vec{a}$ and ...
0
votes
1answer
29 views

Adding a point to shortest path

If there exists a set of n points in a 2D coordinate system and an n-dimensional vector V ...
0
votes
1answer
244 views

Integer Linear Programming (ILP): NP-hard vs. NP-complete?

I was thinking about examples where a problem is NP-hard but was not NP-complete and ILP came to mind. It is obviously NP-hard but is it NP-complete? I.e., is it in NP? Given a certificate (the ...
2
votes
1answer
238 views

Maximizing the number of non-crossing lines between a number of points

Suppose I have a number of points in 2-dimensional space. I want to draw as many lines between the points as possible such that no two lines cross. Hoping for a polynomial time algorithm, I ...
5
votes
1answer
191 views

Complexity of a quadratic program

I have a quadratic program: $$\displaystyle\min_{\mathbf{X}} (\mathbf{X^TQX +C^TX}) \quad{} \text{subject to} \quad{} \mathbf{A X \leq Y}$$ $\mathbf{Q}$ is positive definite and is $N \times N$, ...
6
votes
2answers
593 views

Optimization Puzzle

You are given a large number of LEGO blocks of size 1. You can build blocks of other sizes using smaller blocks. For example, you can build a block of size 2 using two of size 1 blocks and then build ...
4
votes
1answer
148 views

Vertex arrangement on the unit sphere

The problem is how can I solve a following in polynomial time? There is a graph $G$ with $n$ vertices, and the goal is to find an arrangement of its vertices on an $n$-dimensional unit-sphere so as to ...
3
votes
1answer
427 views

Question about the simplex method complexity

So I know that in general the simplex method for linear and convex quadratic programming can require exponential time. But assuming a positive semidefinite quadratic program that is solvable by the ...
2
votes
1answer
60 views

Specific solvable cases of TSP

Did a quick search on polynomial time solvable TSP and found some references such as this one for special cases for the bottleneck TSP. Was wondering if anyone was aware of any references that catalog ...