# Questions tagged [partition-problem]

The tag has no usage guidance.

82 questions
Filter by
Sorted by
Tagged with
55 views

### Is this edge-partitioning NP-Hard?

Let $G = (V,E)$ be an undirected graph with $m = |E|$ edges (assume that $m = 3t$ for some $t \in \mathbb{N}$). Problem: Partition $E$ to $q = \frac{m}{3}$ sets $S_1,S_2,\ldots, S_q \subseteq E$ sets ...
98 views

### Complexity and Algorithm for specific Vertex Separator Problem

Given a graph $\Gamma=(V,E)$ with vertex set $V$ and edge set $E$ a $\textit{three partition}$ is decomposition of $V$ into a triple $(V_1, S, V_2)$ such that vertices of $V_1$ are only incident to ...
77 views

### A simultaneous FPTAS for both max-min and min-max number partitioning

The multiway number partitioning problem has two optimization variants: in one variant the goal is to minimize the largest bin sum (the "makespan"), and in the other variant the goal is to ...
70 views

### Is this Knapsack/Subset Sum Variant NP-Hard?

The problem: Let $A_1 = \{a^1_1,\ldots,a^1_n\}, A_2 = \{a^2_1,\ldots,a^2_n\}, \ldots, A_k = \{a^k_1,\ldots,a^k_n\} \subset \mathbb{N}$ be $k$ sets of $n$ integers, and let $U,L \in \mathbb{N}$ be ...
56 views

### Bin Covering problem with variable bin sizes

I have a decision problem that I cannot seem to map to a standard studied problem, although it seems similar to a few. I am wondering if anyone has come across this problem before, or if someone can ...
1 vote
122 views

### 3 Matroid Intersection, a Special Case

It is well known that finding a maximum cardinality (or weight) common independent set in the intersection of 3 matroids is APX-Hard. Question: Does this problem remain NP-Hard if one of the matroids ...
62 views

### Partition of a set of integers into subsets where the max. of the subset-sums is minimum

Let $S$ be a set of $n$ positive integers, and $p$ be a partition of $S$ into $m$ mutually disjoint subsets, such that no subset contains more than $k$ elements. Let $\mathcal{P}$ denote the set of ...
56 views

### hardness of partition of permutation into a minimum number of monotone subsequences

Given a permutation P, a monotone subsequence is a subsequence (i.e. the elements do not have to be consecutive in P) that increases or decreases. This leads naturally to the following optimization ...
1 vote
201 views

### Graph partitioning to minimize sum of intra-partition edge weights

I've seen a lot of graph partitioning algorithms w/ the objective of minimizing the weight of inter-partition edges, (e.g. k-way partitioning) but haven't quite found anything on minimizing the total ...
104 views

Given a graph $G=(V,E)$ on $n$ vertices and $0 \leq \delta \leq 1/2$, we can define the expansion of $G$ over small sets: $$h(G,\delta)= \min_{\vert S\vert \leq \delta n } \phi(S) \ ,$$ with $$\phi(... 1 vote 0 answers 55 views ### Partition of multisets of polynomials Problem: Given a multiset S of irreducible polynomials in Z[x], say YES if S can be partitioned into two nonempty multisets A and B such that both the product of all the elements of A and the product ... 2 votes 0 answers 79 views ### Is the following special case of multiway number partitioning NP-hard? The following problem is a decision problem of multiway number partitioning (wikipedia) (Note that k is also a part of an input in the following problem, while k is a fixed number in wikipedia ... 4 votes 0 answers 138 views ### Split a string of positive numbers into substrings with decreasing totals Suppose we're given a string of n positive numbers and asked to split it into the maximum number of substrings whose totals are decreasing. I have an O(n) time DP algorithm, but is it already ... 2 votes 0 answers 58 views ### Complexity of a matrix partition problem in graphs All graphs in this question are finite, simple, and undirected. Let H be a regular graph on at least five vertices, let v_1,v_2,\dots,v_n be the vertices in H, and let M be the adjacency ... 0 votes 0 answers 54 views ### Using bin-packing algorithms to approximate maximum-makespan Bin-packing (BP) and maximum-makespan (MM) are dual problems. In both problems, the input can be defined as a set S of positive integers, and the output is a partition of S. In BP, there is a ... 0 votes 0 answers 40 views ### Bin Packing And Preemptive Multi-Core Scheduling I am trying to solve a preemptive multi-core scheduling problem, where the input is the tasks. The number of cores M can be decided after seeing the input tasks. I ... 8 votes 1 answer 229 views ### Finding vertex separator such that the induced subgraph has minimal number of edges My problem is related to edge and vertex cuts with a little twist. Given a graph G and two vertexes u and v. I want to find a set of vertexes S \subset V that disconnects u and v such that ... 3 votes 0 answers 90 views ### Number of connected partitions (or labelings) in a grid graph Let G be a 2D lattice graph (undirected) of size W\times H. Each "inner" vertex has 4 adjacent vertices, whereas "boundary" vertices have 2 or 3 adjacent vertices, ... 4 votes 0 answers 47 views ### Minimal partition covering? I am working on a problem that arises in the design of experiments. I wonder if it is part of a well-studied class of problems. The problem is: Start with a set of points S and a target partition of ... 1 vote 2 answers 288 views ### Two valued variant of subset sum problem I'm interested in the complexity of the following problem: Given a multiset S containing only two positive integers a and b, find a k-partition of S that maximizes the sum of part with ... 1 vote 2 answers 126 views ### Name of this graph partitioning problem? (related to coloring) Given a graph G=(V,E) and an integer k, find a partition P_1, P_2, \dots, P_k of V into k parts that minimize the total number of edges between two vertices in the same part, i.e. \sum_i |(... 2 votes 2 answers 275 views ### Partitioning a connected polygon into connected pieces of equal area Armaselu and Daescu (TCS, 2015) present algorithms that, given a convex polygon P and an integer m (which must be a power of 2), return a partition of P into m convex polygons with the same ... 0 votes 1 answer 323 views ### A k-approximation to k-way number partitioning The k-way number partitioning problem accepts as input a multiset S of positive numbers, and returns a partition of S into k subsets such that the subset sums are as nearly-equal as possible, ... 0 votes 0 answers 188 views ### 3-partition problem without the restriction to triplets In the standard 3-partition problem, there are 3 m integers, their sum is m T, and they have to be partitioned into m subsets of sum T and size 3. Consider the variant without the ... 2 votes 0 answers 113 views ### a direct polynomial reduction from 3EQU-SUM to EQU-SUM problem [closed] Given a multiset of integers S, in the Equ-Sum problem we want to check whether or not S can be divided into two disjoint subsets, say X_1, X_2 such that \sum_{x_i \in X_1}x_i = \sum_{x_j \... 2 votes 1 answer 106 views ### Can the Banach-Tarski paradox be "realized" by floating-point round-off? The Banach-Tarski paradox says that a ball in \mathbb{R}^3 can be partitioned into a finite number of pieces, whose rearrangement has a larger volume than the original. It occurred to me that it ... 2 votes 1 answer 111 views ### NP hard proving: separate graph into a set of the same size disjoint parts by maximizing the shared neighbours of each part Given a graph G=\{V,E\} where V denotes the nodes and E denotes edges. The size of the node |V| = nk. The target is to separte the graph into n disjoint parts P=\{V_i\}_{i=1}^n and the ... 6 votes 1 answer 243 views ### Uniformly sampling or counting connected graph partitions with any number of blocks Question: Is it possible to uniformly sample in polynomial time from the set of all connected partitions of a graph? Or is there a JVV type argument that proves this to be NP-hard? To clarify: By a ... 3 votes 1 answer 112 views ### Meet of integer partitions An integer partition of n, A, is a multiset of positive integers such that \sum_{a \in A} a= n. We say that B \leq A, if there exists a map \phi: |B| \to |A|, such that for a \in A, we ... 6 votes 2 answers 164 views ### NP-Completeness of \epsilon-balanced graph partitioning for fixed \epsilon Consider this graph partitioning problem: Let G = (V, E) be a simple undirected graph and 0 \leq \epsilon \leq 1, M \geq 0 be constants. Are there disjoint subsets V_1, V_2 with V = V_1 \cup ... 8 votes 1 answer 325 views ### A partition problem with order constraints In the OrderedPartition problem, the input is two sequences of n positive integers, (a_i)_{i\in [n]} and (b_i)_{i\in [n]}. The output is a partition of the ... 2 votes 0 answers 76 views ### Hardness result or reference for a set partition problem I'm wondering if the following problem is (or has been proven to be) NP-Complete. Input: integer n\ge0, set S_1,S_2,\ldots,S_{2n}, set T_1,T_2,\ldots,T_n. Accept iff: there exists \{a_i,... 2 votes 0 answers 73 views ### Partition into c and 1-c 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 ... 8 votes 3 answers 918 views ### A partition problem in which some numbers may be cut In the standard partition problem, we are given some numbers whose sum is 2s and have to decide whether they can be partitioned into two subset whose sum is s. It is known to be NP-hard. However,... 6 votes 2 answers 914 views ### Is this partition problem strongly NP-complete? Some computational problems have variants that appear to be harder. For instance, Graph Automorphism (GA) problem has quasi-polynomial time algorithm ( by Babai's Graph Isomorphism result) while the ... 2 votes 0 answers 53 views ### Min cut problem on unbalanced partitions for planar graphs with unit capacity edges The question is: given a planar graph G with unit capacity edge weights and a fixed positive integer k, what is an approximation algorithm for finding the minimum size of a cut (A,B) with |A|=k... 2 votes 1 answer 248 views ### Optimal partition according to partition cardinality Given N sets of integers S_1, \ldots,S_N with |S_i| \le K. We want to partition those sets such that the union of all sets in any given partition doesn't contain more than K elements. Can ... 2 votes 0 answers 181 views ### Is Non-linear Constrained Optimal Exact Cover NP-Hard? Playing around I ran into a problem which looks like a Exact Set Covering / Partition Problem, but I am unable to find a reduction to categorize the complexity of the problem, despite it looks NP-Hard.... 2 votes 0 answers 112 views ### Unbalanced connected partition Let G = (V, E) be a connected graph with (possibly negative) vertex weights w(v)\in\mathbb{Z}. We want to partition the vertices into two parts such that the induced graphs G' and G'' are ... 1 vote 2 answers 251 views ### Complexity of a variant of partition problem Motivated by this post, Strongly NP-complete variants of subset sum or partition problem, I am interested in this variant of partition: Given a solution to balanced partition problem (both parts have ... 3 votes 2 answers 1k views ### Strongly NP-complete variants of subset sum or partition problem Some problems have variants that appear to be harder. For instance, Graph Automorphism (GA) problem has quasi-polynomial time algorithm ( by Babai's GI result). However, the fixed-point free GA ... 0 votes 1 answer 174 views ### Is pooling-aware bin packing NP-Hard? I am unable to prove whether the following problem is NP-Hard. It seems like a bin-packing or a partition problem, without being close enough to either of them (at least I do not see the reduction to ... 2 votes 0 answers 216 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 can divide vertices in ... 4 votes 1 answer 486 views ### Proof that the graph optimization problem is NP-hard I'm trying to prove that the following optimization problem is NP-hard: Given a graph G=(V,E), non-negative vertex weight functions w(v) and s(v), and a non-negative edge weight function t(u,v)... 2 votes 1 answer 381 views ### Partition refinement in transition state systems (bisimulation contraction) I am trying to understand bisimulation contraction of Kripke models. I have read these lecture slides and this Wikipedia page, but I still don't fully understand it. I can understand that the two ... 1 vote 1 answer 273 views ### Maximal Clique partition of vertices with smallest number of cut edges I am given a simple undirected graph G(V, E). I want to partition V into b Maximal cliques: \{C_1, C_2, ..., C_b\} such that the number of edges that cut across two cliques is the minimum. b ... 2 votes 1 answer 1k views ### Max-sum graph-partition for maximizing intra-edge weights? I would like to know if the following problem has already been studied, and if so how is it called. In particular I'm interested in approximability results. Input: A graph G with negative or non-... 3 votes 1 answer 426 views ### Variant of Subset Sum Problem with Changing Bound Given a sequence of decreasing integers, i.e., a_1 \geq a_2 \geq \cdots \geq a_T  and a positive real k\geq 1, find a subset S such that$$\max_{S\subseteq \{1,\ldots,T\}} \sum_{i\in S} a_i...
Assume you have $N$ bags of apples that you want to equally distribute to $K$ people. Each bag contains $n_i$ apples and you are not allowed to open and divide the bags; you must distribute the bags ...