Questions tagged [partitions]

A partition or partitioning of a set A is a collection of disjoint sets whose union yields A.

Filter by
Sorted by
Tagged with
19 votes
5 answers
4k views

"partial sorting" algorithms (aka "partitioning")

Context: When trying to tame real-world datasets that contain outliers and noise, the interquartile mean is a handy tool: you sort the data, throw away the top and bottom 25% of the data and take the ...
fearless_fool's user avatar
19 votes
1 answer
450 views

Problems for which algorithms based on partition refinement run faster than in loglinear time

Partition refinement is a technique in which you start with a finite set of objects and progressively split the set. Some problems, like DFA minimization, can be solved using partition refinement ...
Juho's user avatar
  • 22.6k
11 votes
1 answer
1k views

What is a compact way to represent a partition of a set?

There exist efficient data structures for representing set partitions. These data structures have good time complexities for operations like Union and Find, but they are not particularly space-...
cberzan's user avatar
  • 213
9 votes
2 answers
363 views

Is the ABC-partition problem NP-hard?

In the ABC-partition problem, there are three sets $A, B, C$ with $m$ positive integers in each. The sum of all integers is $m T$. The goal is to construct $m$ triplets with the same sum $T$, each of ...
Erel Segal-Halevi's user avatar
8 votes
1 answer
719 views

Partition problem with distinct integers

The partition problem is a well-known NP-complete problem. In the definitions I have seen, the input is assumed to be a multiset of integers, and we want to decide the existence of a partition into ...
Mohammad Al-Turkistany's user avatar
7 votes
1 answer
293 views

What is the trick of "adding a huge number" for in the reduction from 3-Partition?

Problem: To prove the $\textsf{NP-Completeness}$ of the problem of "Packing Squares (with different side length) into A Rectangle", $\textsf{3-Partition}$ is reduced to it, as shown in the following ...
hengxin's user avatar
  • 9,551
7 votes
1 answer
976 views

Fastest known algorithm for $3$-$\mathrm{Partition}$ problem

$3$-$\mathrm{Partition}$ problem is $\mathsf{NP}$-Complete in a strong sense meaning there is no pseudo-polynomial time algorithm for it unless $\mathsf{P=NP}$. I am looking for the fastest known ...
user avatar
6 votes
1 answer
111 views

Partitioning bag of sets such that each set in a group has a unique element

Suppose I have a bag (or multiset) of sets $S = \{s_1, s_2, \dots, s_n\}$ and $\emptyset\notin S$. I wish to partition $S$ into groups of sets such that within each group each set has at least one ...
orlp's user avatar
  • 13.4k
6 votes
1 answer
169 views

Partitioning an undirected, unweighted, square planar graph paths that join certain pairs of nodes

I am trying to find a way to efficiently solve a puzzle that I play a lot by turning it into a graph partitioning problem (which is basically is in its actual form). I know that generally, graph ...
saltthehash's user avatar
6 votes
1 answer
926 views

Dividing a weighted planar graph into $k$ subgraphs with balanced weight

I've been looking for an algorithm which divides an undirected, weighted, planar and simple graph into $k$ disjoint subgraphs. Here, the graph is sparse, $k$ is fixed, and there are no negative edge ...
davidbsp's user avatar
5 votes
1 answer
4k views

Data structure for partition of a set

A partition of a set S is a separation of the set into an arbitrary number of non-empty, pairwise disjoint subsets whose union is exactly S. What manner of a data structure should be used to represent ...
user avatar
5 votes
1 answer
3k views

Is the set partitioning problem NP-complete?

I know that the set partitioning problem defined like this: Given $$S = \left\{ x_1, \ldots x_n \right\}$$ find $S_1$ and $S_2$ such that $S_1 \cap S_2 = \emptyset$, $S_1 \cup S_2 = S$ and $\...
SashaGreen's user avatar
5 votes
1 answer
3k views

Reduction from PARTITION to MAX-CUT

I am trying to prove the NP-Hardness of the MAX-CUT problem. Other sources seem to reduce from the NAE-3SAT problem, however I have been trying to reduce from PARTITION because PARTITION and MAX-CUT ...
Dave White's user avatar
5 votes
1 answer
84 views

NP-hardness even with perturbations

Consider the following problem, which can be called "2-SET-PARTITION": Given two sets of positive numbers, $a_1,\ldots,a_n$ and $b_1,\ldots,b_n$, where $\sum_{i\in[n]}a_i = \sum_{i\in[n]}b_i = 2 S$,...
Erel Segal-Halevi's user avatar
5 votes
1 answer
202 views

Optimal partitioning of n-tuples

Motivation Recently I was trying to optimize some API calls and reduced the problem to optimization of a cumulative number of identifiers across all the requests. I put some considerable effort into ...
Jendas's user avatar
  • 223
5 votes
0 answers
702 views

How to distribute items of varying sizes into bins of varying sizes, such that percent utilization across all bins is minimized?

I have a bunch of databases, each having different access patterns, such that each puts a different amount of load on its database cluster. I would like to distribute them around my set of database ...
spiffytech's user avatar
4 votes
2 answers
2k views

Hardness proof of EVEN-ODD PARTITION

The PARTITION problem is NP-complete: INSTANCE: finite set $A$ and a size $s(a) \in \mathbb{Z}^+$ for each $a \in A$ QUESTION: Is there a subset $A' \subseteq A$ such that $\sum_{a \in A'} s(a) = \...
Vor's user avatar
  • 12.5k
4 votes
2 answers
87 views

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$

I am trying to think of how to optimize the following problem: Let $S = \{1,2,...,N\}$. How many ways can $S$ be partitioned into non-empty subsets $P_1$ and $P_2$ such that $sum(P_1) = sum(P_2)$? I ...
briancaffey's user avatar
4 votes
1 answer
302 views

Parition a multiset of numbers into two subsets, how to maximize the sum of their medians?

Given a multiset $S$ of numbers, partition it into two subsets $S_1 $ and $S_2$. How to maximize the sum of their medians? For example, the median of {1,2} is ...
Voyager's user avatar
  • 187
4 votes
2 answers
202 views

Equal partition up to one integer

In the partition problem, the task is to partition $n$ given integers into two subsets $A$ and $B$ with equal sum. This problem is known to be NP-hard, but it becomes easy if the "equal sum" ...
Erel Segal-Halevi's user avatar
4 votes
1 answer
206 views

Variant of (WEAK) PARTITION with 2 distinct solutions

I am interested in the complexity of the following problem: Input: A list $a_1\leq ⋯ \leq a_n$ of positive integers. Question: Are there two vectors $x, x'\in\{−1,0,1\}^n$, with at least one $x_i$ ...
user2370336's user avatar
4 votes
1 answer
104 views

Minimum weighted arithmetic mean partion?

Assume I have some positive numbers $a_1,\ldots,a_n$ and a number $k \in \mathbb{N}$. I want to partition these numbers into exactly $k$ sets $A_1,\ldots,A_k$ such that the weighted arithmetic mean ...
Listing's user avatar
  • 205
4 votes
1 answer
345 views

Partitioning a graph into connected pairs and triplets

We need to partition an undirected graph into connected subgraphs of size between $2$ and $k$, where $k$ is an integer. When $k=2$, the problem is equivalent to the perfect matching problem which is ...
Chaya's user avatar
  • 71
4 votes
1 answer
162 views

Can almost equal partition problem be solved in polynomial time?

Given a list of positive integers with sum $s$, decide if there is a subset with sum $0.5s$. This is the well-known PARTITION problem, which is NP-hard. What about the following: Given a list of ...
user355066's user avatar
4 votes
1 answer
65 views

Partitioning a set so both parts have sum at least $c$ times the total sum

Let $c\in(0,1/2]$ be a constant. Given a set of positive integers with sum $S$, is there a partition into two subsets such that both subsets have sum at least $cS$? If $c=1/2$, this is the famous ...
user52378's user avatar
4 votes
1 answer
999 views

3 dimensionnal matching to partition transformation

We want to transform $3DM$ to $PARTITION$, I am reading Garey and Johnson book and I really don't understand how they do the transformation, I know how they create elements $a_i$ from triples of set $...
HFA's user avatar
  • 43
4 votes
0 answers
83 views

How to sample a perfect partition uniformly at random?

I would like to sample $n$ integers (of some fixed length, say $k$ bits) uniformly at random, and have them partitioned into two sets of equal sum. Since finding such a perfect partition (even if it ...
Erel Segal-Halevi's user avatar
4 votes
0 answers
846 views

Even distribution algorithm

Right now I am working on a distributed system that sends messages from single source to many nodes. It is necessary that certain messages are sent to the same node to ensure order of processing. ...
Christopher Reid's user avatar
4 votes
0 answers
284 views

Graph optimization problem with multiple objectives/constraints

Let's assume that we have a directed acyclic graph $G = (V, E)$, non-negative vertex weight functions $w_a(v)$ and $w_b(v)$, and a non-negative edge weight function $t(u,v)$. We want to divide ...
marszall87's user avatar
3 votes
1 answer
755 views

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

I'm trying to randomly allocate N indistinguishable items over B indistinguishable bins with unlimited capacity. Each allocation should occur with equal probability. An allocation identifies the ...
programonkey's user avatar
3 votes
1 answer
125 views

Proving that an equal partition does not exist

We are given a set of $n$ numbers and want to know whether it can be partitioned to two sets with an equal sum. To prove that an equal partition exists, it is sufficient to show a partition. What is ...
Erel Segal-Halevi's user avatar
3 votes
1 answer
70 views

Computing minimum partition of poset of $N$ intervals into chains in $o(N^{2.5})$ time?

Consider a set $P$ of $N$ intervals $\{I_i = (l_i, r_i)\}$ partially ordered according the standard interval order: $I_i < I_j$ iff $r_i \le l_j$. I want to find a minimum cardinality partition of ...
dysonsfrog's user avatar
3 votes
1 answer
317 views

Finding partition with maximum number of edges between sets

Given a graph (say in adjacency list form), is there an algorithm to find a partition of vertices such that the number of edges between the two sets of the partition is the maximum possible? For ...
ab123's user avatar
  • 207
3 votes
2 answers
1k views

Is finding Kth largest element using selection algorithm taking O(n) only if K is fixed?

Wikipedia here https://en.m.wikipedia.org/wiki/Selection_algorithm shows an algorithm using sort of quicksort.. in order to find Kth largest or smallest element taking O(n) time only on average. The ...
Barushkish's user avatar
3 votes
2 answers
663 views

How to prove the NP-completeness of 15-Partition Problem

I would like to have a proof of the NP-completeness for 15-Partition Problem. It is analogous to the well-known 3-Partition Problem. The problem is to decide whether a given multiset of integers can ...
Ondřej Šubrt's user avatar
3 votes
1 answer
8k views

What exactly (and precisely) is "offset"?

Just like my previous question concerning 'hash'; what exactly is an (or the) "offset?" Is it a value or data type? Or is it an address location? I have heard it used in different contexts within the ...
Basil Ajith's user avatar
3 votes
1 answer
1k views

Complexity of variation of partition problem

I want to know whats the complexity of the following variant of the partition problem: Partition problem: http://en.wikipedia.org/wiki/Partition_problem Suppose we have one set formed by integers ...
rotia's user avatar
  • 759
3 votes
1 answer
273 views

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

In the Partition problem, there is a set of integers, and the goal is to decide whether it can be partitioned into two sets of equal sum. This problem is known to be NP-complete. Suppose we are given ...
Erel Segal-Halevi's user avatar
3 votes
1 answer
90 views

Is there an efficient algorithm for WEAK-PARTITION?

Suppose that we are given a list of non-zero integers $(a_1,...,a_n)$ and we want to decide whether there exist $(x_1,...,x_n)$ such that $x_1a_1 + x_2a_2 + ... + x_na_n = 0$, $x_i$ $\in$ $\{-1,0,1\}...
Kevin's user avatar
  • 168
3 votes
1 answer
266 views

Bounded bin covering problem

This all seems fairly related to the knapsack problem, bin packing and the subset sum problem, but I can't find the appropriate problem name. I have a multiset $S$ of $n$ (not necessarily unique) ...
orlp's user avatar
  • 13.4k
3 votes
1 answer
1k views

Cost of partitioning in quicksort

I'm reading "Algorithms Fourth Edition" by Sedgewick & Wayne and am wondering if I have spotted an error in the book or if I just can't wrap my head around something so simple. When talking about ...
Levi Botelho's user avatar
3 votes
1 answer
110 views

Subset sum with only two item types

Suppose we have $r$ copies of the integer $a$ and $t$ copies of the integer $b$, and a capacity $C$. We would like to find the maximum sum of the given integers, that is at most $C$. This is a special ...
Erel Segal-Halevi's user avatar
3 votes
1 answer
179 views

Partition of a $k$-partite graph to minimal number of connected sets

Let $G$ be a $k$-partite directed acyclic graph where the edges are only between two adjacent sets of vertices. I'm trying to partition the graph to the minimal number of connected sets. Sets $A_0, ...
Philip L's user avatar
3 votes
1 answer
190 views

Is there an FPTAS for 3-way number partitioning?

The maximization problem of the 3-way number partitioning reads as follows: given $n$ positive integers, partition them into 3 subsets such that the smallest sum is as large as possible. It is known ...
Samuel Bismuth's user avatar
3 votes
1 answer
326 views

Conditions under which the 3-partition problem is not strongly NP-complete?

I'm a bit confused about the 3-partition problem. More specifically I'm confused about this from the Wikipedia article: Let B denote the (desired) sum of each subset Si, or equivalently, let the ...
Adam Ierymenko's user avatar
3 votes
1 answer
1k views

Algorithm for computing partitions of a set of n elements into subsets of size m

I need an algorithm that can compute all the different partitions of a set of n elements into subsets of size m. For example for $n=4$ for the set $\{a,b,c,d\}$ and $m=2$ the output should be $\{\{\{...
Martin's user avatar
  • 131
3 votes
1 answer
158 views

Partitioning planar graphs without minimizing edge cuts

I am looking for an algorithm that, given an undirected, planar graph $G = (V,E)$ with node weights, meets the following conditions: Creates balanced (within some margin) $k$ partitions of $V$ ...
soandos's user avatar
  • 1,143
3 votes
1 answer
71 views

Partition a graph into connected subgraphs of 3 vertices each

We need to partition a graph into subgraphs of 3 vertices each, such that every subgraph has at least 2 edges. The problem is similar to the partition into triangles problem (which is NP-complete) but ...
Chaya's user avatar
  • 71
3 votes
2 answers
585 views

Proof that Balanced Partition is NP-complete

In the Balanced Partition problem, there are $2m$ nonnegative integers with sum $2s$. The goal is to decide whether they can be partitioned into two subsets of $m$ integers and sum $s$. The problem is ...
Erel Segal-Halevi's user avatar
3 votes
1 answer
49 views

Smoothed analysis of the Partition problem

I am studying smoothed analysis and trying to apply it to the Partition decision problem: given $n$ real numbers with a sum of $2 S$, decide whether there exists a subset with a sum of exactly $S$. ...
Erel Segal-Halevi's user avatar