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 ...
user avatar
  • 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 ...
user avatar
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: ...
user avatar
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'|$. ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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-...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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$ ...
user avatar
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 ...
user avatar
  • 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, ...
user avatar
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)$...
user avatar
  • 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 ...
user avatar
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, ...
user avatar
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$ ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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....
user avatar
  • 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. ...
user avatar
  • 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, ...
user avatar
  • 8,143

Only top scored, non community-wiki answers of a minimum length are eligible