Skip to main content

# Tag Info

## Hot answers tagged optimization

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 ...
• 17.8k
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 ...
• 299
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 ...
• 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 ...
• 17.8k
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 ...
• 127
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 ...
• 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.
• 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 ...
• 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{...
• 429
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 \nu = c^T x^* = (Ay^*-v)^Tx^* = {...
• 429

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