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 ...
user avatar
  • 7,127
9 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 ...
user avatar
  • 11k
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 ...
user avatar
  • 140k
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 ...
user avatar
4 votes
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 ...
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 ...
user avatar
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 ...
user avatar
  • 739
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 ...
user avatar
  • 12.3k
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$ ...
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, ...
user avatar
  • 33k
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. ...
user avatar
  • 22.1k
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.
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 ...
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, ...
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 ...
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 ...
user avatar
  • 937
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 ...
user avatar
  • 2,072
3 votes
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_{...
user avatar
  • 46
3 votes
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'...
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 ...
user avatar
  • 140k
3 votes
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 ...
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 ...
user avatar
  • 2,072
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.
user avatar
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 ...
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 ...
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 ...
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 = ...
user avatar
  • 1,319
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 ...
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 ...
user avatar
2 votes
Accepted

Permute the subintervals of an interval partition to most closely align with a model partition

You can use integer linear programming (ILP) to solve this. In particular, here is how to use an ILP solver to test whether there exists a way to permute the second partition so that you find $k+1$ ...
user avatar
  • 140k

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