Partitioning tuples

Given are tuples $ (a_{11},\dots,a_{1k}), (a_{21},\dots,a_{2k}), \dots, (a_{n1},\dots,a_{nk})$ . We want to know if there is a partition of the tuples into two parts, so that for every coordinate $ i=1,\dots,k$ , the sum of each part is equal to the sum of the other part.

Has this problem been studied before? If $ k=1$ , it is of course the famous Partition problem. But I cannot find this generalization under the section “Variants and generalizations” in the Wikipedia page.

Problem related to set partitioning

Let $ A_j=\{(a^i_j,b^i_j)~:~ 0 \leq i \leq n,\text{and } a^i_j,b^i_j \in \mathbb{Z}^+\}$

Given sets $ A_1,\ldots, A_{p}$ and a positive integer $ k$ , the problem is to check whether there exists one element $ (a^{i_j}_j,b^{i_j}_j)$ from each $ A_j$ such that $ \sum_{j}^{} a^{i_j}_j \geq k$ and $ \sum_{j}^{} b^{i_j}_j \geq k$ .

It looks like the problem is related to set partitioning problem, however, I am not sure how to get a reduction from set partitioning problem. Can someone help me to find the algorithm to solve this problem?

Number partitioning targeting ratio of subset sums and equal size

I’ve seen a number of questions and answers related to the partitioning problem of dividing a set into 2 subsets of equal size and sum that use greedy or dynamic programming solutions to get approximate answers. However, I am looking to split a set into 2 subsets of minimum difference in size but with a target ratio of sums.

I have tried variations of greedy algorithms that will work to minimize the largest difference of the two metrics at any point in the calculation, but this just results in a result that splits the difference between the two. I’m happy with an approximate solution since it needs to run in a reasonable amount of time.

Dynamic Program to solve an NP-complete partitioning problem

I have this problem for which I am struggling to find an efficient dynamic programming algorithm. Would be thankful for some help!!

Let $ A = \{ a_1, a_2, …, a_n \}$ be a set where $ a_i \in \mathbb{N}$ for $ i=1,…,n$ .

The goal is to determine whether there exist two disjoint subsets $ M,N \subset A$ such that the sum of all elements in $ M$ is equal to exactly $ \textit{twice}$ the sum of all elements in $ N.$

Partitioning bag of sets such that each set in a group has a unique element

Suppose I have a bag (or multiset) of sets $ S = \{s_1, s_2, \dots, s_n\}$ and $ \emptyset\notin S$ . I wish to partition $ S$ into groups of sets such that within each group each set has at least one element not found in any other set in that group. Formally, the criterion for a group $ G = \{g_1, g_2, \dots \} \subseteq S$ is:

$ $ \forall i: \left(g_i \setminus \bigcup_{j\neq i} g_j\;\neq\;\emptyset\right) $ $

The partition $ P = \{\{s_1\}, \{s_2\}, \dots\}$ always satisfies this requirement, so there is always a valid solution. But what is the smallest number of groups needed? Is this problem feasible or NP-complete?

Another formulation of this problem is to partition a multiset of integers into groups such that each integer has a bit set in its binary expansion that no other integer in its group has set.

Interval partitioning problem different approach – arrange lectures in minimum number of classrooms

The problem of scheduling lectures in minimum number of classrooms is as follows: Find minimum number of classrooms to schedule all lecture so that no two occur at the same time in the same room.

The common algorithm that I find in books is:

Sort intervals by starting time so that s1 ≤ s2 ≤ ... ≤ sn. d ← 0 //number of classrooms for j = 1 to n {  if (lecture j is compatible with some classroom k)  schedule lecture j in classroom k  else  allocate a new classroom d + 1  schedule lecture j in classroom d + 1  d ← d + 1 } 

Now, I was thinking of an alternate approach where I sort my lectures by finishing times in ascending order and every time I check if lecture j is compatible with some classroom k and there are multiple classrooms that are compatible with that lecture, I schedule it in the classroom which the last jobs finish time in that classroom is closest to that jobs start time, i.e minimise the time a classroom is empty.

Sort intervals by starting time so that f1 ≤ f2 ≤ ... ≤ fn. d ← 0 //number of classrooms for j = 1 to n {  if (lecture j is compatible with some classroom k)  schedule lecture j in classroom k which was used last  else  allocate a new classroom d + 1  schedule lecture j in classroom d + 1  d ← d + 1 } 

I would like to know if this approach is right(not necessarily optimal). I have dry run it on a couple of cases, and looks to be okay. If yes, how can I prove its correctness? If not, how can what changes can I make the algorithm work.

MSHYBRID / NVIDIA Optimus mode for partitioning GPU work?

I purchased a high-end laptop with an RTX 2070 (not max q) to help run my pytorch models. This laptop comes with a BIOS feature called MSHYBRID (Same as NVIDIA Optimus by another name). I read some posts about MSHYBRID mode. To enable it, I had to add GRUB_GFXPAYLOAD_LINUX=1920*1080 to grub. After that, I now have the option in my NVIDIA Settings to switch between discrete (NVIDIA) and Intel integrated graphics. If I switch from one to the other, it makes me logout and then back in to switch GPUs.

However, it’s my understanding that MSHYBRID/Optimus allows Intel to drive the display and NVIDIA to be used secondarily. This is what I want. I want Intel to drive my display and PyTorch/Tensorflow to be able to use my RTX 2070 for compute purposes. That way, I can train models with no disruption to things like video playback. When I run nvidia-smi with MSHYBRID enabled, it says:

NVIDIA-SMI has failed because it couldn't communicate with the NVIDIA driver. Make sure that the latest NVIDIA driver is installed and running. 

This doesn’t sound like what I want. I continued installing CUDA on this new machine anyway. I run:

import torch torch.cuda.get_device_name(0) 

output: 'GeForce RTX 2070'

So I switch to MSHYBRID mode, logout and back in. Trouble starts:

>>> import torch >>> torch.cuda.is_available() False >>> torch.cuda.device_count() 0 

I’m pretty sure this would work in Windows. Often, this feature is used in order to power the display by Intel while simultaneously rendering via the NVIDIA GPU. I believe in Windows it is software controlled. Am I missing something – some linux project to make it work? Can it work?

Messed up my partitioning installation, now windows can’t boot. What do I do?

I have windows 7 installed. I guess I deleted a partition that didn’t have system written on to free up some space for root , /home and swap. But somehow I can’t revert back to its original state and the installation even failed. Now I can’t boot my windows and I guess all my files are gone too. I still have windows recovering system but it doesn’t want to do anything. Anyone knows how to recover the files?