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
0 votes
1 answer
25 views

Shortest paths in $k$-partite DAG

Let $D(V, A)$ be a $k$-partite DAG; $P = \{ p_k : 1 \leqslant k \leqslant |P| \}$ such that $p_k \cap p_l = \emptyset$, $\forall k,l : k \neq l$, and $\bigcup_{1 \leqslant k \leqslant |P|} p_k = V$ ...
Matheus Diógenes Andrade's user avatar
2 votes
1 answer
36 views

Optimally partitioning the reciprocals of the first n integers

Do we know anything about the hardness of the optimization version of the multiway number partitioning problem when the set of numbers to partition consists of the reciprocals of the first $n$ ...
Alex Frechette's user avatar
2 votes
1 answer
62 views

Covering a graph with M cliques maximizing total edges weight

I am working on a problem that involves distributing a set of N supplements across a predefined number of meals (M) in a way that maximizes the total number of positive interactions and minimizes ...
essacult's user avatar
2 votes
1 answer
46 views

NP-hardness of partitioning into k sets

Given a multiset $S$ of positive integers and a fixed positive integer $k$, can $S$ be partitioned into $k$ parts with equal sum? For $k = 2$, this is the well-known Partition problem. For general $k$,...
user166511's user avatar
2 votes
0 answers
27 views

How does this partitioning problem map to studied problems?

I have a real-world (see background below) problem wherein a set $S = \{A,B,C,D...\}$ needs to be partitioned into set $P = \{ \{A,B\},\{D\},\{E,F\},\{C,G,H\},...\}$ where $P$ is required to have the ...
cms's user avatar
  • 121
0 votes
1 answer
63 views

$k$-way number contiguous partitioning

Given a set $S$ of $n$ positive integers $S=\{a_1,\ldots,a_n\}$, can we partition $S$ into $k$ subsets of equal sum such that each subset has contiguous elements from $S$? Here, a contiguous subset is ...
zebda's user avatar
  • 109
1 vote
0 answers
38 views

Algorithm for grouping set items into ordered buckets without crossing boundaries between same set items

I'm trying to order some data in real-time (in an API call) where my item count is on the order of a few million. I'm using Go, so my pseudo code may resemble that. My input items look like this: <...
contrapsych's user avatar
1 vote
0 answers
37 views

Graph partitioning in 2 clusters minimizing between cluster edges

I've been looking for an algorithm which divides an undirected graph into 2 subgraphs. However, unlike most existing work on graph partitioning out there (like METIS), I don't intend to obtain ...
koch_kir's user avatar
0 votes
0 answers
38 views

List of weakly NP-HARD problems

I need a list of at least 10 weakly NP-HARD problems. I already know the Knapsack problem, partition problem and subset sum problem. Please introduce other weakly NP-hard problems to me.
Soroush Vahidi's user avatar
0 votes
0 answers
64 views

Hoare's partition original method

So I was reading the Hoare's partition part of the Quicksort wiki and it says: "With respect to this original description, implementations often make minor but important variations. Notably, the ...
Reggie Hurley's user avatar
2 votes
1 answer
160 views

Partition of two sets for multi-line fitting, NP-hard?

Given two sets of nonnegative numbers $X=\{x_1,...,x_n\}$ and $Y=\{y_1,...,y_n\}$, my problems consists in finding the partition $S \subseteq \{1,...,n\}$ and $\bar{S}=\{1,...,n\}\backslash S$ ...
T. Pmp's user avatar
  • 43
0 votes
0 answers
21 views

reduction from partition to N3DM or balanced 3 partition problem

I want to know how can I reduce Subset Sum or Partition problem to N3DM problem in which each set has exactly 3 elements and same sum. N3DM Problem: https://en.wikipedia.org/wiki/Numerical_3-...
user's user avatar
  • 1
3 votes
1 answer
68 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
4 votes
1 answer
342 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
3 votes
2 answers
107 views

Does there exist an algorithm / software that finds optimal graph partition while enforcing contiguity on a subgraph?

I am interested in the traditional graph partitioning problem, which roughly speaking seeks to obtain a partition of a graph into a number of components, in which each component has about the same ...
Ike348's user avatar
  • 131
0 votes
1 answer
45 views

Partitioning a set based on a non-equivalence relation

I have a set of $n$ elements, and a binary relation between these elements. However, this is not guaranteed to be an equivalence relation. (Specifically, the elements are line segments in a plane, and ...
Draconis's user avatar
  • 7,078
1 vote
1 answer
42 views

Is deciding whether a graph admits two vertex-disjoint spanning trees of bounded size difference NP-hard?

I'd like to decide whether, given a connected graph $G = (V, E)$ and an integer $k$ as input, $G$ admits two vertex-disjoint subgraphs $T_1 = (V_1, E_1)$ and $T_2 = (V_2, E_2)$ such that $T_1$ and $...
J. Schmidt's user avatar
0 votes
0 answers
25 views

Is there any upper bound for the number of ways we can partition a multiset, where each part/segment in the partition has distinct elements?

A question is asked in the below link, which asks for the number of cases we can partition a multiset, where each part/segment in the partition has distinct elements. https://math.stackexchange.com/...
Amir's user avatar
  • 1
1 vote
1 answer
33 views

Reduction from $2$-Partitioning to (simple) pairwise $2$-Partitioning

I'm currently stuck showing $NP$-hardness of a problem of mine. An instance of my problem (I call it (simple) pairwise $2$-Partitioning) is given by the following: Given a set of tupels $B=\{(b_1,1),\...
Felix's user avatar
  • 161
1 vote
1 answer
33 views

Minimum number of bits to codify arrays with bounded sums

I have a very big set of non-empty arrays of possibly repeated numbers sorted in a weakly-decreasing order where each number belongs to the interval $[1, 55]$ and the sum of the elements of each array ...
ABu's user avatar
  • 529
0 votes
1 answer
57 views

Maximal Profit of 'legal' cutting of a board

I'm facing this problem for some time now, I've tried a greedy approach yet I result to trying a DP-ish approach, only to get stuck at a standstill. Given a board of length $n$, and an increasing ...
Aishgadol's user avatar
  • 345
3 votes
1 answer
749 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
1 vote
1 answer
152 views

The modularity difference in Louvain algorithm for community detection in graphs

I am interested in the formula of modularity difference between two partitions considered in the Louvain algorithm for community detection in graphs. I give a formal expression of this question below. ...
Matthieu Latapy's user avatar
1 vote
0 answers
45 views

Minimize sum of products of partition [closed]

I have a set of positive integer numbers $A = \{a_1,...,a_N\}$ and I need to find a partition of $A$ into two sets, such that the sum of their products is minimal, i.e., $$ \min_{X,Y : X \cup Y = A} \...
DrDizzy's user avatar
  • 11
4 votes
1 answer
158 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
0 votes
1 answer
107 views

Complexity of the partition problem with additional constraint

The "classical" partition problem asks whether a given multiset $S$ of positive integers can be partitioned into two subsets $S_1$ and $S_2$ such that the sum of the numbers in $S_1$ equals ...
NoteMyQuestion's user avatar
1 vote
1 answer
33 views

Set partitions into singletons or pairs

I am trying to build an algorithm to compute the partition of a set into singletons or pairs for a set of cardinality 16. I am doing it in MATLAB and came up with codes that either run forever or ...
Cesare's user avatar
  • 113
1 vote
0 answers
46 views

Split Bipartite Graph

I have a bipartite graph $G=(U=\{U_1, U_2,\cdots\}, V=\{V_1, V_2,\cdots\} , E)$ such that edges don't "skip" the $V$ vertices. Meaning, if edge $(U_i, V_j)$ doesn't exist, neither will edges ...
Jon Nir's user avatar
  • 143
1 vote
0 answers
22 views

"Icebreaker problem": Dividing set into partitions that maximize pairwise shared memberships?

Suppose I have a set of N*L elements. I wish to generate a sequence of k partitions of size L such that I maximize the number of pairs of elements that share membership of the same partition. What ...
Katie's user avatar
  • 163
1 vote
1 answer
470 views

How to partition N numbers into K groups with constraints on the size and sum of each group?

Suppose we are asked to assign $N$ numbers into $K$ mutually exclusive groups. The partition has to satisfy two constraints for each group. The first one is that group $k$ must contain exactly $n_k$ ...
szx's user avatar
  • 13
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
0 votes
1 answer
42 views

Partitions with subsets of limited cardinality

Is there a way to compute the number of partitions such that each set in the partition has a cardinality lower or equal to two? If yes, is there also an efficient algorithm to compute these partitions?...
Cesare's user avatar
  • 113
1 vote
1 answer
54 views

Partition data into two sets of the same size such that the sum of the average distances is maximized

Say I have a set of strings $S=\{s_1, s_2, ..., s_N\}$, and I want to partition $S$ into two sets $S_1$ and $S_2$ equally, i.e., $||S_1|-|S_2||\leq1$. Define the difference of a set as $$Diff(S_k)=\...
h_axlrose's user avatar
3 votes
2 answers
555 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
0 votes
0 answers
27 views

Is there an algorithm to efficiently generate all partitions of a set such that no cell contains fewer than k elements of the set?

I am trying to generate partitions of networks to evaluate clustering algorithms. I know that generating all partitions is infeasible (since they grow with Stirling number of the second kind which get ...
user023049's user avatar
1 vote
0 answers
45 views

Proof that there isn't a $c$-additive approximation to Partition Problem

Define Partition to consist of all tuples $x_1,\ldots,x_n$ which can be divided to two groups in which the sums of the two groups are equal. Is there a proof that there isn't an additive approximation ...
yellowcard123's user avatar
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 ...
Voyager's user avatar
  • 187
0 votes
0 answers
27 views

Efficient way of partitionning a set into a fixed number of parts

I am looking for a way of efficiently partitionning a set of consecutive integers in to a set where the number $K$ of parts is given. For instance, for the set {1, 2, 3, 4}, I would like the best way ...
user7060's user avatar
  • 465
1 vote
1 answer
38 views

Similar problem to Subset Sum?

I've been trying to search for a problem which I think could be similar to Subset Sum. The definition of the problem would be as follows: Given k $\in$ $\mathbb{Z}$ and S = {$s_1$,...,$s_n$} s.t. $s_i ...
Maitgon's user avatar
  • 23
2 votes
0 answers
167 views

Is it known whether PARTITION is NP-complete via first order reductions?

The PARTITION decision problem is defined as follows (taken from COMPUTERS AND INTRACTABILITY from Garey and Johnson): Instance: A finite set $A$ and a size $s(a) \in \mathbb{Z}^{+}$ for each $a \in A$...
Paúl Risco's user avatar
1 vote
0 answers
2k views

Split the given array into K subsets such that maximum sum of all subsets is minimum

Given an array of $N$ elements, $A$, and a number $K$. ($1 \leq K \leq N$) . Partition the given array into $K$ subsets (they must cover all the elements but can be noncontiguous too). The maximum ...
Ashkan Khademian's user avatar
1 vote
0 answers
36 views

Computational Hardness of the $k$-Partition Problem with identical numbers/objects?

The $k$-Partition Problem is NP hard. I want to know if some slight modification of this problem makes it polynomially solvable. Now consider the set $S=\{a_1,\ldots,a_n\}$ of IDENTICAL numbers/...
NoteMyQuestion's user avatar
0 votes
0 answers
103 views

Partition a graph into subgraphs such that a partition contains up to X number of a particular node type

I have a DAG graph which contains two types of nodes, A and B. I am looking for a graph partitioning algorithm that can partition a graph in sub-graphs such that each sub-graph contains up to X number ...
user145024's user avatar
2 votes
0 answers
35 views

Partition columns into m groups to maximize absolute value sums

The Task You are given $n$ columns each of length $m$. All values are either $-1$ or $1$. Find an assignment $s$ of each of columns to 1 of $m$ groups in order to maximize the sum of all the absolute ...
k-0348's user avatar
  • 21
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 ...
Erel Segal-Halevi's user avatar
1 vote
1 answer
623 views

Partition a set of n integers into m subsets in a way that the maximum subset sum is minimized

Let's say we have a set of n integers. I'm trying to find a way to partition this set into m subsets (empty subsets are not ...
Fish_n_Chips's user avatar
2 votes
1 answer
55 views

Upper-bounding the out-going degree of a graph

Given a graph $G=(V,E)$, I'm looking for a way to orient its edges in a way that will bound its out degree. For example, I can bound the graph's out-degree by $\approx 2\cdot a(G)$, where $a(G)$ is $G$...
TheEmeritus's user avatar
1 vote
0 answers
157 views

Does an FPTAS exist for the multiple subset sum problem when m is fixed and c is not a variable?

From Wikipedia Multiple subset sum: The multiple subset sum problem (MSSP) is a generalization of the subset sum problem (SSP): given a multiset $S$ of $n$ integers, and an integer $m$, the goal is to ...
Samuel Bismuth's user avatar
1 vote
1 answer
720 views

SUBSET SUM reduction to PARTITION

This is the PARTITION problem: Given a multiset S of positive integers, decide if it can be partitioned into two equal-sum subsets. This is the SUBSET SUM problem: Given a multiset S of integers ...
Legend123's user avatar
  • 113
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 ...
Erel Segal-Halevi's user avatar