Skip to main content
11 votes

What is the fastest static comparison sort? What is the proper term for "static"?

The answer by Display name explains why the model trivializes. However, let me add some pointers to established terminology: A query-based algorithm is called nonadaptive if all the oracle queries ...
Emil Jeřábek's user avatar
7 votes

What is the fastest static comparison sort? What is the proper term for "static"?

The reason this question isn't in the literature is because $m = \frac{n(n-1)}{2}.$ Suppose we know the order between every element except WLOG, between $\sigma(1)$ and $\sigma(2).$ It is impossible ...
Display name's user avatar
4 votes
Accepted

Is beta normalization used for program optimization?

Short answer: $\beta$-reduction is done like crazy in any modern optimizing compiler. As you can easily check e.g. for GHC. The caveat is that $\lambda$s usually serve no useful purpose in the ...
cody's user avatar
  • 13.9k
3 votes
Accepted

Is Optimal Swap Sorting NP-Hard?

Even though the authors do not explicitly formulate it that way, the paper [1] (the reference mentioned in the OP) does actually prove the NP-completeness of bounding the minimal number of swaps ...
Emil Jeřábek's user avatar
2 votes

What is the fastest static comparison sort? What is the proper term for "static"?

Assume all array elements are different. If two items are consecutive in the sorted array, then they must be compared to each other, otherwise we cannot know which one should come first. And since we ...
gnasher729's user avatar
2 votes
Accepted

Given a weighted graph with $pk$ nodes find a min weight forest with $p$ components each containing exactly $k$ nodes

There is no poly-time approximation algorithm for this problem unless P=NP. For the metric case (when the graph is complete and the edge weights satisfy the triangle inequality), there is a poly-time ...
Neal Young's user avatar
  • 10.8k
2 votes

Maximum cardinality disjoint cycle cover in undirected graphs

Well, if there is a disjoint triangle cover of $G$ then this would be the cycle cover of maximum cardinality. And it is NP-hard to determine if there is a disjoint triangle cover.
JimN's user avatar
  • 1,318
1 vote

Given a weighted graph with $pk$ nodes find a min weight forest with $p$ components each containing exactly $k$ nodes

I think I can show that the problem is NP-hard, even in the case where the graph is unweighted. Specifically, given an undirected graph $G$, and values $p$ and $k$, I want to know if I can partition ...
a3nm's user avatar
  • 9,517
1 vote
Accepted

Linear Programming Sensitivity to Matrix

Okay I think I have figured this out! I am going to assume we have primal and dual problems: \begin{array}? (P) &&\max& c^Tx &&& (D) &&\min& b^Ty \\ &&\text{...
NaturalLogZ's user avatar
1 vote

Linear Programming Sensitivity to Matrix

Let $u$ and $v$ be vectors of slack variables for the primal and dual, respectively. Thus $A x^* + u = b$ and $A^T y^* - v = c$. Then we can see that \begin{equation} \nu = c^T x^* = (Ay^*-v)^Tx^* = {...
NaturalLogZ's user avatar

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