# Tag Info

Accepted

### "partial sorting" algorithms (aka "partitioning")

The algorithm quickselect can return the $k$-th value of an unordered array in average linear time. It can be "improved" (though not so much in practice) using the median of medians to ...

### "partial sorting" algorithms (aka "partitioning")

There are a couple of algorithms which are useful for this particular problem. Although they are usually described as selection algorithms, which compute the $k^{th}$ order statistic of an unordered ...
Accepted

### Proving that an equal partition does not exist

The current expectation is that most likely there is no efficient (polynomial-size, polynomially-verifiable) way to do that. The partition problem is NP-complete. For a NP-complete problem, we have ...
Accepted

### What's the purpose of Karger's algorithm?

Even in an unweighted graph, your suggested algorithm doesn't work: take a graph of 6 vertices with triangle a, b, c, and triangle d, e, f, with an edge between c and d. Vertices a, b, e, and f each ...
Accepted

### Minimum weighted arithmetic mean partion?

Suppose first that we fix the sizes of the sets $|A_i| = n_i$ in non-decreasing order $n_1 \leq \cdots \leq n_k$. In that case, if we arrange the numbers $a_i$ in non-decreasing order, then an optimal ...

### What exactly (and precisely) is "offset"?

An offset is a difference between two indices, usually memory locations or array indices. For example, suppose that you have an array $A$ in which each element occupies $x$ bytes. Suppose also that ...

### How to prove the NP-completeness of 15-Partition Problem

I think this could work. We multyply all the numbers by fifteen and we also multiply $B$, the quantity that each "bucket" should add to, by fifteen and we add twelve to it. Then we add twelve numbers ...
Accepted

### Finding the number of ways to partition $\{1,...,N\}$ into $P_1$ and $P_2$ such that $sum(P_1) = sum(P_2)$ for a given $N$

Hint: find a recurrence $f(n, k)$ that tells you in how many different ways you can sum to $k$ using the first $n$ integers (ignoring order and using numbers at most once). Then the answer to your ...
Accepted

### sub-optimal but fast partition generation

The following is directly taken from pages 358-360 of The Nature of Computation by Moore and Mertens and I think addresses your problem directly. Imagine that you run a computer center with $p$ ...
Accepted

### Can interval partition solve by sort by different approach

Yes, your approach is correct. "The interval partitioning problem" is more commonly known as "the interval-graph coloring problem". It is problem 16.1-4 in the book Introduction to Algorithm by CLRS, ...
Accepted

### Finding partition with maximum number of edges between sets

If your question really is "is there an algorithm", the answer is obviously yes: just try every possible partition and choose the one maximizing the number of edges with endpoints in different parts. ...
Accepted

### Computing minimum partition of poset of $N$ intervals into chains in $o(N^{2.5})$ time?

Your problem is the same as interval graph coloring. There is a well-known greedy algorithm solving the problem optimally, running in linear time if the intervals are already sorted.
Accepted

### Computing the partition function

Johansson gave a nearly linear time algorithm (in terms of the output size!) in his paper Efficient implementation of the Hardy-Ramanujan-Rademacher formula. This work is mentioned at the very end of ...

### Partitioning a graph into subgraphs with overlapping nodes

I never heard of any algorithm with the constraint of having an overlap between communities larger than a given threshold (4 here). But I suggest the following: turn your graph into its line graph, ...
Accepted

### Parition a multiset of numbers into two subsets, how to maximize the sum of their medians?

Your algorithm is correct. The following is its proof of correctness. Let $S_1$ and $S_2$ be the optimal partitions of $S$. Let their medians be $m_1$ and $m_2$. Let the maximum element is $M$ that ...

### "partial sorting" algorithms (aka "partitioning")

is there a "partial sorting" algorithm that is more efficient than a full sort that will yield those three groups? Since you're talking about "real-life" scenarios rather than ...

### Enumerate partitions of a set with blocks of equal size

Section 5.10 of Ruskey's book Combinatorial Generation gives a combinatorial Grey code for linear extensions of posets and describes a bijection between set partitions of a chosen shape and linear ...
Accepted

### Minimize sum of squared error

You are looking for an optimal 1-dimensional k-means algorithm. The k-means objective function for partitioning the data $x_1, \ldots, x_n$ into $k$ sets $S = \{S_1, \ldots, S_k\}$.  \sum\limits_{...
Accepted

### Complexity of variation of partition problem

Is it in NP? Yes - any restricted version of an NP problem is also in NP. Is it still NP-hard? Yes. 2-partition (without the constraint that both subsets should be equal cardinality) is NP-hard. Let'...
Accepted

### Bounded bin covering problem

When $k,s$ are upper-bounded by a constant, the problem can be solved in polynomial time. Call a multiset $T$ good if its sum is at least $s$, and if removing any one element causes the sum to fall ...
Accepted

### Cost of partitioning in quicksort

This is a pretty common version of partition and in this case you need N+1 comparisons. For example consider an array containing ${1,2,\ldots,N}$. Now, 1 is your pivot (partitioning item). pivot 1 ...
Accepted

### An algorithm for k-way array partitioning

I can't even figure out how to do it out of place, other than allocating n dynamic sized arrays and finally concatenating them together. Which is the approach used by the explanation in Wikipedia, so ...
Accepted

### Is there an efficient algorithm for WEAK-PARTITION?

Your problem is NP-complete, as proved by Adi Shamir in his paper On the cryptocomplexity of knapsack systems.
Accepted

### Karp hardness of directed monochromatic triangle problem

All directed graphs can be edge-partitioned into two subgraphs that are acyclic and therefore triangle free. Let $\prec$ be any total ordering of the vertices. For each edge $(u, v) \in A$, put it in ...
Accepted

### Partition array into k subsets

I'm assuming by $sum(i)$ you mean that given an ordering of the $k$ partitioned subsets, sum over all elements of the $i$th subset. The $k=2$ case is the optimization variant of the set partitioning ...
### Partitioning a set so both parts have sum at least $c$ times the total sum
The problem is polynomial (even linear time) for any fixed $c < 1/2$. Assume no there is no item of size $> (1-c)S$, otherwise it is a trivial no-instance. If there is any item $w_i$ with size ...