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 ...
- 12.5k
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 ...
- 11.9k
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.♦
- 156k
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.♦
- 156k
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 ...
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 ...
- 275k
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 ...
- 749
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 ...
- 12.7k
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$ ...
- 1,048
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, ...
- 38.6k
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.
...
- 22.5k
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.
- 275k
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 ...
- 275k
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, ...
- 625
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 ...
- 5,827
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 ...
- 965
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.♦
- 156k
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.
- 275k
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 ...
- 2,072
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 ...
- 2,072
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 ...
- 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 ...
- 782
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 ...
- 13.2k
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 = ...
- 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 ...
- 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 ...
- 5,459
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$ ...
- 2,205
3
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 $...
- 5,827
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 ...
- 206
2
votes
Accepted
Sampling among constrained partitions
A reflexive, symmetric and transitive relation $R$ on $O$ is the same as a partition of $O$. If $(o_i,o_j) \in R$ then $o_i,o_j$ are in the same partition, and so can be merged. If $(o_i,o_j) \notin R$...
- 275k
Only top scored, non community-wiki answers of a minimum length are eligible