# Questions tagged [partitions]

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

35 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
909 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 ...
639 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 ...
657 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. ...
249 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 ...
100 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 ...
134 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 ...
84 views

### Schedule X Classes In N Classrooms

I would really appreciate any thought on this, or under which category does this problem fall (Interval scheduling, Interval partitioning,...) I am really out of thoughts I have X number of classes ...
24 views

### Seeking an algorithm for finding the partition of data on an interval that maximizes the minimum fitness among the blocks

In the paper "An algorithm for optimal partitioning of data on an interval" (link) the authors describe an algorithm for partitioning data on an interval to maximize a fitness function. The fitness ...
18 views

### Is there a more commonly-used term for “multi-pivoting”?

Consider the following computational problem (or rather, task): Given: An array of $A$ of (not necessarily distinct) elements from a fully-ordered finite domain An ordered sequence pivot ...
1k views

### k-way set partition problem--dynamic programming solution

I was reading up on the set partition problem on this site of Wikipedia: https://en.m.wikipedia.org/wiki/Partition_problem Among other things, they present a DP approach to solving the equal subset ...
174 views

### Reducing partition to a partition where sum(partition1) = 3 times sum(partition2)

Given the following NP-complete problem: PARTITION Input: A list of positive integers $a_1, a_2, \dots, a_n$. Question: Can the list be partitioned into $2$ parts, $A_1$ and $A_2$, such ...
148 views

### min cut for multiple partitions

So I am familiar with the standard minimum cut problem in which the goal is to find the smallest possible set of edges in a graph such that, upon their removal, we have two nonempty, disjoint ...
22 views

### Partition graph in a way that minimizes inter-partition edges

I have a graph in which certain vertices are labeled. I need to assign labels to all of the other vertices in a way that minimizes the number of edges between different-label vertices. How can I do ...
121 views

### Prove Product Partition is NP-complete in the strong sense

I am trying to understand how to prove that the Product Partition problem is NP-complete in the strong sense. The problem is similar to the normal Partition problem, except in this case the product of ...
16 views

### Balanced $\epsilon$-separated partitioning by a hyperplane

Suppose we have $m$ points in $R^n$ and $\epsilon>0$ is a given constant. How can we find a hyperplane that the number of points that are $\epsilon$-close to it is minimum, with the constraint that ...
43 views

570 views

### Exact algorithm for the partition problem

The partition problem is: given a set of numbers, find a partition to two subsets in which the difference between the sums in each subset is minimized. This optimization problem is NP-hard. The simple ...
179 views

### Computational Geometry: what is the key of the BST in the algorithm “ Partitioning a polygon in y-monotone pieces”

The algorithm to partition a polygon into y-monotone pieces is as follows: ...
183 views

### Non-standard partition problem

I've been writing codes to solve a standard partition problem. I've investigated brute force, greedy, Karmarkar-Karp and complete Karmarkar-Karp algorithms. Standard partition problem: divding a ...
89 views

42 views

### Quicksort with lomuto partition - how many repeating elements are too many?

I know that quicksort with Lomuto's partition method faces worst case run-time $\Theta(n^2)$ when there are many repeating elements in the array. However, I'm trying to figure out - how many ...
21 views

### Find the max partition of unique elements where each element corresponds to the set pool containing that element

Given a list of sets: a b c -> _ c d -> d b d -> b a c -> a a c -> c The objective is to find the max partition of unique elements with ...
77 views

### Directed Acyclic Graph partition into minimum subgraphs with a constraint

I have this problem, not sure there is a name for it, wherein a Directed Acyclic Graph has different colored nodes. The idea is to partition it into minimum number of subgraphs with the following 2 ...
19 views

### Evaluating clustering/partitioning quality

I'm wondering what are the most common/recognized methods to assess the quality of a clustering. That is because I have developed a tool that can cluster/partition a network (in this case, a public ...
102 views

### $k$-partitioning problem via brute force

Given a set of non-negative integers $A = \{a_1,a_2,\dots,a_N \}$, the $k$-partitioning problem is to partition the numbers into $k$ sets $\{A_1,A_2,\dots, A_k\}$ such that the deviation:  \...
70 views

### Is a minimal deviation version of set partition problem NP-Hard?

I want to know if a specific version (and what´s its name?) of the Set Partitioning Problem is NP-Complete, and if, is NP-Hard? Problem: Given a set of elements $e_i$ where $i={1,...,n}$, each with ...
168 views

### Reduction from 3-Partition to a cutting problem

My problem is the following: Input: a set of $m$ non-negative integers $\{b_1,...,b_m\}$ and a parameter $n$ with $n<m$. Output: $n$ sets of 3 numbers Task: Cut the $b_i$'s into $3n$ integers such ...