43
votes
Accepted
Is it a rule that discrete problems are NP-hard and continuous problems are not?
An example that I love is the problem where, given distinct $a_1, a_2, \ldots, a_n \in \mathbb{N}$, decide if: $$\int_{-\pi}^{\pi} \cos(a_1 z) \cos(a_2 z) \ldots \cos(a_n z) \, dz \ne 0$$
This at ...
- 2,295
26
votes
Is it a rule that discrete problems are NP-hard and continuous problems are not?
There are many continuous problems of the form "test whether this combinatorial input can be realized as a geometric structure" that are complete for the existential theory of the reals, a continuous ...
- 50.2k
15
votes
Easy to optimize but hard to evaluate
Here is an example, where one can produce a solution in polynomial time, but evaluating a given solution is NP-hard.
Input: Positive integers $n,k$ (in unary encoding), with $k\leq n$.
Task: ...
- 10.7k
14
votes
Accepted
Is the following graph optimization problem approximable within a constant factor?
The problem is very similar to Min Uncut. In Min Uncut, given a graph $G = (V, E)$, we need to find a subset of edges $E'$ s.t. $G - E'$ is bipartite; the objective is to minimize the size of $|E'|$. ...
- 3,844
13
votes
Is it a rule that discrete problems are NP-hard and continuous problems are not?
While this doesn't exactly answer your original question, it's a (conjectural) example of a sort of philosophical counterpoint: a problem where the presentation is discrete but all of the hardness ...
- 1,346
10
votes
Is it possible to optimize the calculation of $ax+b$ once I know $a$ and $b$?
I would rephrase the question as follows:
Consider the function $F$ and the family of functions $F_{a,b}$ defined as
$$F_{a,b}(x) = F(a,b,x) =ax+b.$$
Can we compute $F_{a,b}$ faster than the ...
- 21.3k
10
votes
Accepted
Find research partner (profession and beginner)
I don't know of such a page. Most researchers have specific problems that they are interested in working on, and would only want to collaborate on those. If you pick a particular area and focus on ...
- 7,052
9
votes
Accepted
Minimum weight matching in general graphs with additional input specifying the number of matched edges
Add $n-2k$ extra vertices, each connected to all the original vertices with zero-weight edges, and add a large enough number $W$ to each of the original edges to make their weights all positive. Then ...
- 50.2k
9
votes
Accepted
Positivstellensatz and sum of squares method
As already noted in the comments, the question is based on a misunderstanding; the actual Positivstellensatz is a stronger statement than Artin’s theorem on nonnegative polynomials, and the real ...
- 14.8k
9
votes
Accepted
Proof that the graph optimization problem is NP-hard
This problem is in P, it can be reduced to the Minimum cut problem.
The graph construction is as follows - Add a source and a sink vertex. For each vertex $i$, add an edge with cost $w(i)$ from ...
- 126
8
votes
Accepted
Existing benchmarks for scheduling problems?
Mainly, there exist 3 benchmarks to test shop scheduling problems.
Namely they are Taillard, Structured and ORLib benchmarks. These benchmarks have different
goals. The Taillard benchmark is the most
...
- 319
8
votes
Accepted
Quantum annealing vs adiabatic quantum computation
Adiabatic quantum computing (AQC) is a computational model (as Peter said in the comments). Compare AQC with other models of computation such as:
circuit-based quantum computing (CBQC)
Adleman-...
- 540
8
votes
Is it possible to optimize the calculation of $ax+b$ once I know $a$ and $b$?
I think the answer to your question is dependent on the exact setting
of your problem, and in particular the representations you intend to
use for $a$, $b$, and $x$, as well as the available ...
- 1,502
8
votes
Accepted
minimal finite automata given in-words and out-words
If your FSM is a DFA, then this is the Minimum Consistent DFA Problem, which is well known in the machine learning community. This problem is NP complete
Gold1978 - Complexity of Automaton ...
8
votes
Second Smallest $s$-$t$-Cut in a Network
The second smallest cut, and more generally the $k$ smallest cuts, can be found in time polynomial in $k$ and the network size. See:
H. W. Hamacher. An $(K\cdot n^4)$ algorithm for finding the $k$ ...
- 50.2k
7
votes
Fast algorithm for weighted bipartite matching problem
You might try one of the auction-based algorithms for bipartite matchings. (See e.g. lecture notes describing a simple variant here: https://staff.fnwi.uva.nl/n.s.walton/Notes/Bertsekas_Auction.pdf ...
- 9,800
7
votes
Is it a rule that discrete problems are NP-hard and continuous problems are not?
Discrete problems typically tend to be harder (e.g. LP vs. ILP) but it's not the discreteness itself that's the problem... it's how the constraints affect how you can search your domain. For example, ...
- 411
7
votes
Accepted
Finding the two shortest paths while minimizing the number of nearby/common edges
If the cost is $|P_1|+|P_2|+|P_1∩P_2|$, then a simple reduction to the shortest pair edge disjoint paths gives us a polynomial time solution. For each edge $e=(u,v)$ add two edges $(u,uv)$ and $(uv,v)$...
- 3,420
7
votes
Accepted
Is finding an optimal solution to this Knapsack-like problem NP-hard?
NOTE: My original reduction didn't work. Fixed now.
Can't subset-sum be reduced to this problem fairly easily? Suppose all the profits $v_i$ are the same, say $v_i = 1$, and all the profits $p_i$ are ...
- 23.5k
7
votes
Solving linear equations involving min
I assume the generalization you are thinking of is the following:
Given value $d$, and values $s_i$ and $r_i$ for $i = 1,2,...,k$, find (if possible) an $\alpha$ such that
$$\sum_{i = 1}^k\min(r_i, ...
- 2,718
6
votes
Job scheduling: minimizing number of reads
After a failed polynomial-time quick attempt, here it is an idea to prove that it is NP-complete using a reduction from 3SAT.
Given a 3SAT formula with $x_1,...,x_n$ variables and $C_1,...,C_m$ ...
- 22.3k
6
votes
Accepted
On which classes of graphs is resource constrained shortest path (RCSP) NP-hard?
I don't know if you're still interested in this (old) question, and if I understood well the resource constraints you gave in the comment; however it seems that your problem (which is slightly ...
- 22.3k
6
votes
Accepted
Minimal cumulative set sum
This problem is actually related to a scheduling problem knows as "Precedence constrained scheduling to minimize weighted completion time". The problem is as follows : Given a set of jobs, where each ...
6
votes
Reordering data (set of strings) to optimize for compression?
This is an addition to the Navin Goyal's answer.
Since a JSON file can be regarded as a tree data structure, you can use the XBW-transform for trees, which is an extension of the Burrows-Wheeler ...
6
votes
What are some of the most ingenious linear programs developed for tackling hard combinatorial problems?
The relaxation of Calinescu, Karloff and Rabani for the undirected Multiway Cut problem is one my favorites. Had a big influence on subsequent work.
http://www.sciencedirect.com/science/article/pii/...
6
votes
Accepted
What do you call the join of two optimization problems?
I think this falls in the category of multi-objective function optimization problems.
To be specific, it's a linear scalarization of an optimization problem with two objective functions.
I don't ...
- 23.5k
6
votes
Accepted
Minimizing a submodular function given noisy oracle access
A FOCS'15 paper by Lee, Sidford, and Wong [LSW15] can be leveraged to obtain such minimization guarantees -- cf. Section 5 (specifically, Corollary 5.4) in our recent paper ([BCELR16]).
Corollary 5....
- 4,341
6
votes
Accepted
Modifying Edmonds' Blossom Algorithm
You just have to solve the following problem: Find a matching of size exactly $k$ with minimum weight.
It can be solved by reducing to min weight perfect matching. See the paper by Ján Plesnı́k. ...
- 4,256
6
votes
Accepted
Characterization of integral polyhedra
Here's a proof (sketch) that doesn't explicitly use duality. More precisely, it replaces duality by a seemingly weaker (and hopefully easily believable) geometric fact, in Step 3 below.
EDIT: But, ...
- 8,143
Only top scored, non community-wiki answers of a minimum length are eligible