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
2
votes
0answers
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 ...
1
vote
0answers
185 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 ...
0
votes
0answers
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 ...
1
vote
0answers
93 views

DISTINCT 3-PARTITION with all integers between $B/4$ and $B/2$

In the definition of 3-PARTITION of Garey&Johnson, the instance is a set of $3m$ integers such that the sum of all these integers is $mB$ and such that each integer is strictly between $B/4$ and $...
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,...
4
votes
1answer
181 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$ ...
3
votes
1answer
133 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$ ...
1
vote
1answer
3k views

Reduction of SUBSET-SUM to SET-PARTITION [duplicate]

There is a similar question that has been asked, but my question addresses particular detail of an answer. I am trying to reduce SUBSET-SUM to SET-PARTITION. I found the following description: ...
0
votes
1answer
68 views

Which element is at its final position after the partitioning step in Quicksort?

In Algorithms, 4th Edition, I read that after the partitioning step one element is in its final position. The entry a[j] is in its final place in the array, for some j. No entry in a[lo] ...
2
votes
1answer
343 views

Going deeper with pseudo-polynomial time algorithm for set partitioning

If I have a set of (edit) positive integers, and I'm sure that the pseudo-polynomial time algorithm for partitioning the problem will not give me an answer - what would I do next? To illustrate this ...
-1
votes
1answer
489 views

Sorting tuples with respect to multiple criteria

Given $n$ rows with $k$ columns, is there a storage mechanism/data-structure and/or algorithm that enables dynamic restructuring such that I can get the top $t=\mathcal{O}(1)$ results efficiently? ...
0
votes
1answer
762 views

A partition algorithm

I have encountered the following problem that I found very interesting to solve: Given an array of positive integers $\{a_1, a_2, ..., a_n\}$ you are required to partition the array into $3$ ...
7
votes
1answer
207 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 ...
1
vote
0answers
197 views

Enumerate subtrees of a given size in a graph

Given a graph $G$ with $n$ nodes, is there an algorithm to find $m$ subtrees, each with $\lfloor n/m\rfloor$ or $\lceil n/m\rceil$ nodes, such that every node of $G$ is in exactly one tree? Other ...
0
votes
1answer
1k views

Multiprocessor Scheduling is NP-Complete [closed]

Consider this version of MS where we have set $A$ of tasks, $l(a)$, length of each task in $A$ and $m$ number of processors and also a deadline $D$. The question is where we can partition A into m ...
1
vote
0answers
48 views

Graph Partition Across Cluster - Minimize Largest Matrix Size

I am writing some code for modeling semi-biologically realistic neural networks, which is to be run/distributed across nodes in a computer cluster. I begin with a very large adjacency matrix (...
4
votes
1answer
708 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 $...
1
vote
1answer
2k views

Partition partition with constraint of equal size

I see the problem here which is the well know partition problem but with constraint that the size of both sets must be equal. I look at the answer and I don't understand that why Colin said add max(S)...
1
vote
1answer
2k views

Minimize sum of squared error

I have an array of real numbers, I want to partition them into k sets. In each set, I calculate the sum of squared error. Then, I add up all the sum of squared error for all the set. I want to ...
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 ...
-1
votes
1answer
41 views

Algorithm for random generation of two connected partitions of a finite set [closed]

Given the set $X=\{1,2,\ldots,n\}$; $\,\,$ $n=mp=kq$ where $m,k,p,q$ are positive integers. Please help me to programme an algorithm that realizes random generation of the following two partitions of ...
0
votes
1answer
569 views

2-way Graph Partitioning problem

We have a graph $G=(V,E)$ and we need to divide this graph into two clusters $A$ and $B$. Some pairs of vertices $u$, $v$ should not be in the same cluster, and we define an edge $(u,v) \in E$. The ...
2
votes
1answer
291 views

Finding all partitions of a set s.t. each block contains exactly one subset from a given set of subsets - how hopeless?

Hello and apologies if my question will be too elementary. My background is from arithmetic geometry, but I have been recently faced with certain computational problems of combinatorial nature, where ...
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 ...
2
votes
2answers
67 views

Partition area using test function

I am looking for an efficient algorithm that can partition an area $B \subset \mathbb{R}^2$ into disjoint subsets $B = \bigoplus_i U_i$ such that a test function is constant on each of the subsets, $f ...
3
votes
1answer
993 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 ...
2
votes
1answer
1k views

How to find partition set of a Partition Problem using its decision problem

I understand Partition Problem is NP-complete. Given we have a magic black box that can answer Yes or No for the partition problem. I was wondering how to come up with a polynomial time algorithm to ...
4
votes
1answer
92 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 ...
1
vote
1answer
158 views

Permute the subintervals of an interval partition to most closely align with a model partition

You are given two things: A fixed initial 'model' partition of an interval, e.g. I------I---I-----I-------I----... where each ...
-1
votes
1answer
402 views

Balanced partition problem for N =< 60 and very large sums

I was proposed (in school) to develop an approach to solve optimally the balanced partition problem. I tried the pseudo-linear algorithms but SUM is very large (~1M) and so O(S*N) cant run under ...
0
votes
1answer
462 views

Partition points in a plane with a straigth line

Given are a 2D plane and a array of points in this plane, with every point having an integer value assigned. Is there an algorithm which, when given a ratio a/b, divides the plane with a straight ...
4
votes
2answers
848 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) = \...
0
votes
4answers
10k views

Partition array into K subsets, each with balanced sum

Given array $A = \{ a_{1},a_{2}, ..., a_{n}\}$ and integer $k; 0 \lt k \le n$, partition array $A$ into $k$ subarrays, such that $A'_{1} = \{a_{1}, ...,a_{x}\}$ $A'_{2} = \{a_{x+1},...,a_{y}\}$ $......
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
726 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 ...
8
votes
1answer
483 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 ...
11
votes
1answer
867 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-...
7
votes
1answer
913 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 ...
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 ...
5
votes
0answers
644 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 ...
1
vote
1answer
2k views

Showing a partition-like problem is NP-complete

Given a set $A=\{a_{1},a_{2},a_{3},\ldots,a_{n}\}$, then construct a set $P=\{p_{1}, p_{2}, p_{3}, \ldots , p_{n}\}$ such that $|p_{i}|=a_{i}$, and $\sum_{i = 1,}^{n}p_{i} = 0$. This problem is NP-...
20
votes
1answer
425 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 ...
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 ...

1 2
3