# Tag Info

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 ...

### 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 ...

### 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: ...
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'|$. ...

### 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 ...

### 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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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-...

### 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 ...
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 ...

### 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$ ...

### 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 ...

### 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, ...
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)$...
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 ...

### 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, ...

### 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$ ...
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 ...
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 ...

### 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 ...

### 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/...
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 ...
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....
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. ...