The tag has no wiki summary.

learn more… | top users | synonyms

2
votes
2answers
42 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
30 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
72 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 ...
0
votes
1answer
137 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
184 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 ...
2
votes
1answer
300 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 ...
6
votes
0answers
129 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
259 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 ...
10
votes
0answers
170 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 ...
4
votes
1answer
254 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 ...