Share Your Experience: Take the 2024 Developer Survey

# 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 ...
• 15.7k

### "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 ...
• 12k
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 ...
• 161k
Accepted

### Is it possible to randomly allocate items to bins such that each distinct allocation has equal probability?

It appears your question is equivalent to sampling uniformly at random from the integer partitions of $N$, but constrained so that your partition has $\le B$ parts. If that is correct, there are ...
• 161k
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 ...

### 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 ...
• 277k
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 ...
• 13.6k

### 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 ...
• 759
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$ ...
• 1,058
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, ...
• 39k
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. ...
• 22.6k
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.
• 277k
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 ...
• 277k

### 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 ...
• 6,187

### "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 ...
• 975

• 1,339
Accepted

### If a solution to Partition is known to exist, can it be found in polynomial time?

I think the whole misunderstanding comes from an incorrect definition of TFNP. TFNP is for problems like factoring, where there is always a solution. Every integer has a prime factorization, so you ...
• 156
Accepted

### Upper-bounding the out-going degree of a graph

The problem of finding an acyclic orientation with minimum outdegree is equivalent to finding the degeneracy of the graph, which can be solved optimally in linear time. The following algorithm due to ...
• 5,479

### Can almost equal partition problem be solved in polynomial time?

Yes, this problem is polynomial-time solvable. Let $A$ be the input numbers and let $S = \mathrm{sum}(A)$ be its sum. Let $T_1 = 0.49S$, $T_2 = 0.51 S$ be the target sum range. Let $\epsilon = 0.02$ ...
• 2,418
Accepted

### Shortest paths in $k$-partite DAG

If $|p_k|\leqslant N$ for all $k\in \{1, …, |P|\}$, then a dynamic programming algorithm can compute all those distance in $\mathcal{O}(|V|^2\times N)$ which could be lesser than $|V|^3$. The idea is ...
• 15.7k
For its complexity, note $N$ the sum of all your integers. Then, the number partitioning problem injects itself into your problem with $K=\frac{N}{2}$ I found this paper which deals with almost your ...