1
vote
1answer
78 views

A certain instance of the Set Covering problem

Is there any useful structure associated with the following instance of the Set Covering problem? Let $G$ be a weighted graph and let $\mathcal{P}$ denote the set of all shortest paths between all ...
1
vote
0answers
100 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: ...
4
votes
2answers
367 views

Simplified knapsack problem

There is a problem that I can not solve. Given a set of items (each item has some integer weight) we have to fill bag with some number of copies of these items, with the only restriction that the ...
0
votes
1answer
218 views

Is unconstrained integer convex optimization problem NP-hard?

Does anyone know a reference to the answer if unconstrained integer convex optimization problem (i.e. $\min_{x\in \mathbb{Z}^N} F(x)$, $F$ is convex and $N$ is NOT fixed) is NP-hard? Thank you in ...
1
vote
3answers
1k views

How to get the largest subset of a set of sets of intervals with no overlapping intervals

Given: Set of Set of Intervals. Example {{(1,2), (3,4)}, {(1, 3)}, {(13,14)}} Wanted Result: Largest Subset, in which no Interval overlaps with another from every Set pairwise. Example: Input ...
2
votes
1answer
132 views

Maximizing positive definite quadratic using the eigendecompoisition

Consider the problem: $\textrm{max}\;\; x^T Q x$ subject to $||x||_\infty \leq 1$, where $Q$ is a positive definite matrix. I believe this problem is NP-hard (although I have only found hardness ...
3
votes
2answers
624 views

Computational complexity of unconstrained convex optimisation

What is known about the relationship between unconstrained convex optimisation and computational complexity? For example, for which optimisation problems and which gradient descent algorithms is one ...
10
votes
1answer
520 views

Complexity of a weirdo two-dimensional sorting problem

Please forgive me if this is easy for some reason. Suppose given $S$, a set of $n^2$ points in $\mathbb{R}^2$. I want to choose a bijective map $f$ from $S$ to the set of lattice points in $\lbrace ...
6
votes
2answers
809 views

Conic hulls and cones

Suppose I have a number of vectors in $\mathbb{R}^n.$ The first question is: what is the most efficient algorithm to compute their "conic hull" (the minimal convex cone which contains them)? The next ...
5
votes
3answers
647 views

SDP Feasibility

I have a decision problem that I have formulated as a feasibility SDP. The answer to the decision problem depends on whether the SDP is feasible or not. It is known that a SDP can be solved to ...
1
vote
2answers
1k views

Greedy approach to 0-1 Knapsack problem in specific instances

The 0-1 knapsack problem is known to be NP-complete, and the greedy approach by Dantzig (based on choosing on the basis of density or value/weight) can be shown to be suboptimal using counterexamples. ...
3
votes
2answers
329 views

Finding the solution to b = Ax that minimizes the Hamming weight (everything over the field F_2).

Is there an efficient algorithm for finding the solution $x$ of $b = Ax$ that minimizes the Hamming weight of $x$, where $A$ is a nxm-matrix over the field $\mathbb{F}_2$ ("integer matrix modulo ...
1
vote
0answers
210 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 ...
1
vote
0answers
362 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$ ...
4
votes
0answers
297 views

Can the Littlewood-Richardson cone be used for combinatorial optimization?

The Littlewood-Richardson cone $LR_{n, k}$ consists of all $k-$tuples $(a_1, a_2, \dots, a_k)$ of real $n-$vectors with monotonically decreasing entries such that there exist $k$ $n \times ...
3
votes
1answer
581 views

Is quadratic programming still NP-hard if you have bounds and a feasible point?

The reason I am wondering this is that all of the reductions from 3-SAT => quadratic programming (or similar NP-hard reductions) involve encoding the underlying NP-hard problem into feasibility ...
2
votes
1answer
223 views

Network flow gadget

Given m units of flow from a source node, and several possible destinations, is there a network flow gadget to force the flow to use only one destination? That is, send all m units to one ...
11
votes
6answers
3k views

Solving NP problems in (usually) Polynomial time?

Just because a problem is NP-complete doesn't mean it can't be usually solved quickly. The best example of this is probably the traveling salesman problem, for which extraordinarily large instances ...