# 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

### 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 ...
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 ...

### 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 ...
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

### 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

### 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 ...

### 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

### 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 ...
Accepted

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 = ... 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 ... 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 ... 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$... 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$...
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 ...
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$...