## 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?

Posted on Categories proxies

## Ant Colony Optimization on Maximum Partitioning Graphs with Supply and Demand

I’m still new to the field of Computer Science and I’m having trouble understanding this paper An ant colony optimization algorithm for partitioning graphs with supply and demand. Can I ask for a simpler explanation of the paper?

Posted on Categories proxies

## 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.

Posted on Categories proxies

## 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.$$

Posted on Categories proxies

## 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.

Posted on Categories proxies

## Is it always possible to retrieve data from a rewritable CD? And using partitioning and formatting discuss their forensic implications

Is it possible to retrieve data from a rewritable CD? Using partitioning and formatting discuss their forensic implications.

Posted on Categories proxies

## 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.

Posted on Categories proxies

## 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?

Posted on Categories Best Proxies

## 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?

Posted on Categories Best Proxies