Questions tagged [partitions]
A partition or partitioning of a set A is a collection of disjoint sets whose union yields A.
195
questions
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 ...
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 ...
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-...
9
votes
2
answers
362
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 ...
8
votes
1
answer
712
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 ...
7
votes
1
answer
292
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 ...
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 ...
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 ...
6
votes
1
answer
168
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 ...
6
votes
1
answer
917
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 ...
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 ...
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 $\...
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 ...
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$,...
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 ...
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 ...
4
votes
2
answers
1k
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) = \...
4
votes
2
answers
86
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 ...
4
votes
1
answer
299
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 ...
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" ...
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$ ...
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
...
4
votes
1
answer
343
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 ...
4
votes
1
answer
159
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 ...
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 ...
4
votes
1
answer
996
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 $...
4
votes
0
answers
80
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 ...
4
votes
0
answers
845
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. ...
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 ...
3
votes
1
answer
754
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 ...
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 ...
3
votes
1
answer
69
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 ...
3
votes
1
answer
300
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 ...
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 ...
3
votes
2
answers
661
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 ...
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 ...
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 ...
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 ...
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\}...
3
votes
1
answer
264
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) ...
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 ...
3
votes
1
answer
108
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 ...
3
votes
1
answer
178
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, ...
3
votes
1
answer
189
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 ...
3
votes
1
answer
314
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 ...
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
$\{\{\{...
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$ ...
3
votes
1
answer
69
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 ...
3
votes
2
answers
565
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 ...
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$.
...