Skip to main content

Questions tagged [partition-problem]

The tag has no usage guidance.

38 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
8 votes
0 answers
816 views

Is this minimization problem NP-Complete?

We are given an $n \times (n + k)$ matrix $A$, with entries in GF(2), of the form $A =[I_n\ B]$, where $I_n$ is the $n \times n$ identity matrix, and $B$ has no "zero" rows or columns. The problem is ...
RIchard Williams's user avatar
7 votes
0 answers
1k views

Partitioning DAG into Paths

What bounds (lower or upper) are known about the complexity of partitioning a Directly Acyclic Graph (DAG) into paths of respective sizes $n_1,\ldots,n_w$, such that to minimize their entropy $n{\cal ...
J..y B..y's user avatar
  • 2,776
7 votes
0 answers
851 views

Approximation results for 3-partition

The 3-partition as defined here is a strongly NP-complete decision problem. Consider one optimization problem of 3-partition where the $m$ subsets each have at most three elements and a sum of not ...
aelguindy's user avatar
  • 951
5 votes
1 answer
154 views

Complexity of the Partition problem in the Real RAM model

The Partition problem is: given $n$ numbers in the range $[0,M]$, decide if they can be partitioned into two subsets with equal sum. If the numbers are integers, then the problem is NP-complete, but ...
Erel Segal-Halevi's user avatar
5 votes
0 answers
86 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 ...
Erel Segal-Halevi's user avatar
5 votes
0 answers
122 views

Variation on block design/set cover

Given 3 parameters $s, r$ and $t$, where $r \leq t$, I want to construct $t$ sets such that each integer $\{1, \ldots, s\}$ appears in exactly $r$ of these sets. The question is: Is it possible to ...
ragip's user avatar
  • 51
4 votes
0 answers
142 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 ...
Travis's user avatar
  • 51
4 votes
0 answers
48 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 ...
CommonerG's user avatar
  • 141
3 votes
0 answers
96 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, ...
Djoudjou's user avatar
3 votes
0 answers
705 views

Graph partition with weighted vertices and edges

I am searching for an algorithm to apply to a specific graph partition problem that I am interested in. It feels like a topic that people from CS may have worked on but it is also different from ...
Kirill's user avatar
  • 31
3 votes
0 answers
2k views

DAG partitioning for parallel computing

Consider a set of processes ($P=\{p_1, p_2,\dots, p_n \}$) and their data dependencies. Each process $p_i$ has an execution runtime which is denoted by $d_i$. We are interested to parallelize these ...
Javad's user avatar
  • 251
2 votes
0 answers
27 views

Hardness of 3-Partition with Small Target Value

In the 3-partition problem, we are given a set of positive integers $a_1,\ldots,a_n$ and a target value $T$; the goal is to decide if there is a partition of the numbers to triplets such that the sum ...
John's user avatar
  • 412
2 votes
0 answers
73 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 ...
Code-searcher's user avatar
2 votes
0 answers
76 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 ...
steven kelk's user avatar
2 votes
0 answers
112 views

Small set expansion and expanders

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(...
loplo's user avatar
  • 41
2 votes
0 answers
98 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 ...
Ryoshun Oba's user avatar
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 ...
Cyriac Antony's user avatar
2 votes
0 answers
77 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,...
Shlw Kevin's user avatar
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 ...
user52378's user avatar
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$...
hnewton 's user avatar
2 votes
0 answers
183 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....
Paul Knight's user avatar
2 votes
0 answers
117 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 ...
jcai's user avatar
  • 121
2 votes
0 answers
217 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 ...
marszall87's user avatar
2 votes
0 answers
178 views

Graph partition with objective over intra-partition weights

I have a problem in which I need to find an optimal graph cut that maximizes an objective over weights not on the cut. I have looked at the literature but have not been able to find any similar ...
user136011's user avatar
2 votes
0 answers
452 views

Post Correspondence Problem "binary" variant

Bounded Post Correspondence Problem is defined as follows: given list of pairs of words $ (x_1,y_1), \ldots, (x_n, y_n) $ and $K$ find sequence of indexes $i_1, \ldots, i_k$, $k \leq K$ so that $x_{...
anacrusis's user avatar
1 vote
0 answers
284 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 ...
axizzt's user avatar
  • 11
1 vote
0 answers
57 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 ...
luciano's user avatar
  • 61
1 vote
0 answers
100 views

Distributing bags of apples equally

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 ...
oceanhug's user avatar
  • 119
1 vote
0 answers
153 views

Array partitioning with limitations on partition size

Consider an array of bytes. I want to partition the array, such that the following two conditions hold: The number of bytes within each partition (except perhaps the last one) is between L and U, ...
Sadeq Dousti's user avatar
  • 16.5k
1 vote
0 answers
58 views

Repartitioning a binary tree

Suppose I have a binary tree $G = (V, E)$ (with undirected edges) that is partitioned into sets of k vertices, where each set of vertices is a connected subgraph of $G$. Additionally, if there are ...
zaloo's user avatar
  • 393
1 vote
0 answers
62 views

Partition planar graph of vertices with at most degree 3 into connected subgraphs

I'm currently working on my thesis which deals with pathfinding over a Delaunay triangulated graph. I want to be able to partition my Delaunay triangulation into disjoint (regarding vertices) ...
zaloo's user avatar
  • 393
0 votes
0 answers
72 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 ...
John's user avatar
  • 412
0 votes
0 answers
64 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 ...
Rohan Bali's user avatar
0 votes
0 answers
61 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 ...
Erel Segal-Halevi's user avatar
0 votes
0 answers
45 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 ...
Blue Granny's user avatar
0 votes
0 answers
205 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 ...
Erel Segal-Halevi's user avatar
0 votes
0 answers
167 views

NP-hardness of minimizing sum of complicated objective function

In our research, we faced the following problem optimization problem: Input: a list of $k$ pairs of positive integers $(n_1,d_1), \ldots, (n_k,d_k)$; an integer $m$. Output: $P$, a partition of the ...
user34956's user avatar
0 votes
0 answers
89 views

Partitioning based on distribution

Having a set of numbers $S={s_i}$, I want to assign them to bins, $b_i$, such that the sum of items on bins follow a specific distribution. For two bins and uniform distribution, this problem is ...
Masood_mj's user avatar
  • 199