Skip to main content
Share Your Experience: Take the 2024 Developer Survey
26 votes
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 ...
Nathaniel's user avatar
  • 15.7k
10 votes

"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 ...
rici's user avatar
  • 12k
7 votes
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 ...
D.W.'s user avatar
  • 161k
7 votes
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 ...
D.W.'s user avatar
  • 161k
5 votes
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 ...
Algorithms with Attitude's user avatar
4 votes

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 ...
Yuval Filmus's user avatar
4 votes
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 ...
orlp's user avatar
  • 13.6k
4 votes

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 ...
rotia's user avatar
  • 759
4 votes
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$ ...
Sebastian Oberhoff's user avatar
4 votes
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, ...
John L.'s user avatar
  • 39k
4 votes
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. ...
Juho's user avatar
  • 22.6k
4 votes
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.
Yuval Filmus's user avatar
4 votes
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 ...
Yuval Filmus's user avatar
4 votes

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, ...
Matthieu Latapy's user avatar
4 votes
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 ...
Inuyasha Yagami's user avatar
4 votes

"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 ...
einpoklum's user avatar
  • 975
4 votes

Partitioning a graph into connected pairs and triplets

The problem can be solved in the polynomial time for $k = 3$. There is this paper by Chen et al.. The authors design an approximation algorithm for the minimum $3$-path partition problem. The minimum $...
Inuyasha Yagami's user avatar
3 votes
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 ...
D.W.'s user avatar
  • 161k
3 votes
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.
Yuval Filmus's user avatar
3 votes
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 ...
Peter Taylor's user avatar
  • 2,082
3 votes

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 ...
Peter Taylor's user avatar
  • 2,082
3 votes
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 ...
Pontus's user avatar
  • 687
3 votes
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 ...
BearAqua in Agua's user avatar
3 votes

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 ...
Tom van der Zanden's user avatar
3 votes
Accepted

Equal partition up to one integer

There is an $O(n \log n)$ algorithm for this problem. To formalize, lets say that the task is to partition $n$ given integers into two partitions $A$ and $B$ that have sizes $a$ and $b$, with $a+b = ...
Laakeri's user avatar
  • 1,339
3 votes
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 ...
Sam's user avatar
  • 156
3 votes
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 ...
j_random_hacker's user avatar
3 votes

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$ ...
pcpthm's user avatar
  • 2,418
3 votes
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 ...
Nathaniel's user avatar
  • 15.7k
2 votes

Subset partition problem variant

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 ...
user5751924's user avatar

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