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
20
votes
1answer
412 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
1answer
845 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-...
8
votes
1answer
463 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
1answer
200 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
1answer
893 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
1answer
92 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
1answer
117 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 ...
5
votes
1answer
3k 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
1answer
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
1answer
2k 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
1answer
67 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
1answer
155 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
1answer
711 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
0answers
627 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
2answers
805 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
2answers
75 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
1answer
175 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
1answer
90 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
2answers
98 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
1answer
53 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
1answer
693 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
0answers
597 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
0answers
243 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
1answer
76 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
1answer
90 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
2answers
402 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
1answer
70 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
1answer
37 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
2answers
430 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
1answer
47 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
1answer
188 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
1answer
935 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
1answer
875 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
1answer
131 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
1answer
30 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$. ...
3
votes
1answer
1k views

Partitions of a directed graph - common prey and common enemy partitions

Let $D=(V,E)$ be a finite directed graph with no isolated nodes(from every node there is at least one edge entering and one exiting). For $v \in V$ define the following sets: $$v^+= \left\{w \in V|(v,...
3
votes
0answers
94 views

Reduction from 3-partition to ABC-partition

The ABC-partition problem is a variant of 3-partition in which, instead of a single set $S$ with $3 m$ positive integers, there are three sets $A, B, C$ with $m$ positive integers in each. The goal is ...
3
votes
0answers
122 views

Split a graph into 2 components with known distribution?

I'm trying to find a method to randomly split a connected planar graph $G$ into two connected components, such that the sum of the weights of vertices in each component are relatively close. (If there ...
2
votes
2answers
174 views

Partitioning a graph into subgraphs with overlapping nodes

I'd like to partition a graph into subgraphs with overlapping nodes. To do a simple partition into two, I could use kernighan_lin_bisection algorithm available in ...
2
votes
2answers
422 views

Enumerate partitions of a set with blocks of equal size

Given a set $\{1,\ldots,ck\}$, is there a known algorithm to efficiently list all partitions in with $c$ blocks of cardinality $k$? In The art of computer programming (Fascicle 3B) by Knuth, there's ...
2
votes
1answer
213 views

Can interval partition solve by sort by different approach

The interval partitioning problem is described as follows: Given a set {1, 2, …, n} of n requests, where ith request starts at time s(i) and finishes at time f(i), find the minimum number of ...
2
votes
1answer
2k views

reducing subset-sum to partition

Subset-sum: Given a list of numbers, find if a non-empty sublist has sum 0 (there's a variation where we want sum=k instead of 0, but 0 is easier for analysis) Partition: Given a list, can it be ...
2
votes
1answer
6k 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 ...
2
votes
1answer
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 ...
2
votes
1answer
21 views

Partitioning tuples

Given are tuples $(a_{11},\dots,a_{1k}), (a_{21},\dots,a_{2k}), \dots, (a_{n1},\dots,a_{nk})$. We want to know if there is a partition of the tuples into two parts, so that for every coordinate $i=1,\...
2
votes
1answer
68 views

How to prove the NP-completeness of MOD-PARTITION

MOD-PARTITION: Given a set of integers $A={a_1,...,a_n}$, their weights $w = \{w_1, w_2, \dots, w_n\}$ and the number $k$, does there exist a subset $X$ of $A$ such that: $(\sum_{x \in X} w(x) * x) \...
2
votes
1answer
153 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 ...
2
votes
1answer
1k views

Solve PARTITION-INTO-THREE-SETS in pseudo-polynomial time

Let PARTITION-INTO-THREE-SETS be defined as following: Input: Positive integers $a_1, ..., a_n$ Problem: Are there three pairwise disjoint sets $I, J, K \subseteq \{1, ..., n\}$ with $I \cup J \cup ...
2
votes
1answer
63 views

finding separating words (Nerode)

i have found the equivalence classes of given $R_L$ and i need to find the separating words between the equivalence classes(which i don't know how to do). would appreciate if you could explain to me ...
2
votes
1answer
70 views

Dijkstra Partitioning Algorithm : Special Case

I have been exploring Dikstra partitioning Algorithm. Below are my given: R = Red W = White B = Blue I have this unpartitioned array. ...