# Questions tagged [partition-problem]

The tag has no usage guidance.

59 questions
Filter by
Sorted by
Tagged with
39 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 ...
109 views

220 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 ...
65 views

278 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 ...
178 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$ ...
762 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-...
308 views

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$$ $$... 0answers 496 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 ... 0answers 74 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 ... 0answers 155 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 ... 1answer 241 views ### How many edges are cut in a balanced partition of a graph? Consider a graph on n nodes and e edges that is partitioned into k "balanced" subgraphs in the sense that each block has an equal number of nodes and the number of cut edges is minimized. Is there a ... 0answers 126 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, ... 1answer 359 views ### NP-hardness of minimizing sum of weighted product Consider a total of d items, \{I_1,I_2,\cdots,I_d\}, each having a weight w_i (a positive integer), and a total of m bins, \{B_1,B_2,\cdots,B_m\}. We would like to distribute the items into ... 2answers 1k views ### Partition planar graph into connected subgraphs of equal size Work Jünger, Michael, Gerhard Reinelt, and William R. Pulleyblank. "On partitioning the edges of graphs into connected subgraphs." Journal of graph theory 9.4 (1985): 539-549. states that for 4-... 1answer 529 views ### What is a minimum vertex separator as in this definition? In a research paper the following definition appears that I'm not able to understand completely. Let G=(V,E) be an undirected unweighted graph with vertex set V and edge set E, no self-loops, ... 1answer 358 views ### Another variant of PARTITION I've got a reduction of the following partition problem to a certain scheduling problem: Input: A list a_1\leqslant\cdots\leqslant a_n of positive integers in non-decreasing order. Question: Does ... 0answers 163 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 ... 0answers 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 ... 4answers 2k views ### Partitioning graphs while minimizing inter-partition edges I'm working on trying to partition a triangulated graph into connected subgraphs with some guarantees on the number of inter-partition edges. Here's an example of a triangulated graph that has been ... 0answers 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) ... 0answers 50 views ### partition into unit-interval graphs [duplicate] I am re-opening this question as i have the following question. I was going through the paper by Farrugia which was mentioned in an answer in that post. Initially i beleived that the follwoing problem ... 1answer 517 views ### Partition into interval graphs Suppose there is a graph G=(V,E). I want to test if V can be partitioned into two disjoint sets V_1 and V_2 such that the subgraphs induced by V_1 and V_2 are unit interval graphs. I know ... 2answers 2k views ### Partition a graph into 2 connected subgraphs I'm stumped on a sub problem that I'm working on for my thesis. I need to be able to partition a graph into 2 connected subgraphs of almost equal size. So if there are m vertices in G, subgraphs ... 0answers 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 ... 1answer 394 views ### Partitioning a matrix into equal-sized regions: finding the maximum I am facing the following research problem. We are given a matrix M[1..p,1..p] of elements such that: each element has value in the range [0, \frac 1 j], j <= p, j is given, the sum of all ... 1answer 149 views ### Planning jobs as partition problem I think this should be a famous problem but I could not find its name. I have n jobs with size s_i that are offered at time t_i and k machines. How can I assign jobs to machines to minimize ... 1answer 98 views ### what problem is this? [closed] I have this instance: Let's say I have two (could be more) friends, one weighing 200 pounds and another weighing 100 pounds; I won a box with 30 chocolates in a contest and I want to divide among ... 0answers 915 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 ... 0answers 119 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 ... 1answer 210 views ### Expansion vs Sparsest cut let G=(V,E) and S\subsetneq V then expansion of set S is$$\alpha(S)=\frac{|E(S,\overline{S})|}{\min\{|S|,|\overline{S}|)\}} where $\bar{S}=V\setminus{S}$ and $E(S,\bar{S})$ are edges ...
Given $n$ items and $m$ customers, each of whom is interested in some subset of the items, partition the set of items among $k$ different stores so that the maximum number of customers visiting any ...