Is Edmonds’ Matroid partitioning algorithm optimal w.r.t lexicographical order?

We all know that, given a matroid $ (E, \mathcal{I})$ , Edmonds’ Matroid partitioning algorithm will result in a tuple of $ E$ -covering, pairwise-disjoint independent sets $ (I_1, …, I_k)$ with optimal (smallest) $ k$ .

Assume the sizes of $ I_j$ are decreasingly sorted: $ |I_1| \ge \; … \; \ge |I_k|$ .

My question: Is $ (|I_1|, …, |I_k|)$ optimal (largest) w.r.t the lexicographical order of the lexicon $ \mathbb{Z^+} = \{ 1 < 2 < 3 < … \}$ .

If this is NOT the case, is there any algorithm finding a tuple of $ E$ -covering, pairwise-disjoint independent sets $ (I_1, …, I_k)$ with the optimality of $ (|I_1|, …, |I_k|)$ ? Potentially it may sacrifice the optimality of $ k$ .

Balanced $\epsilon$-separated partitioning by a hyperplane

Suppose we have $ m$ points in $ R^n$ and $ \epsilon>0$ is a given constant. How can we find a hyperplane that the number of points that are $ \epsilon$ -close to it is minimum, with the constraint that it partitions the points to two sets of equal size. More formally, if the hyperplane is parametrized by $ u^\top x = b$ , in which $ ||u||_2=1$ is the unit vector orthogonal to the hyperplane. The constraint is that the number of points that is in the halfspace $ u^\top x<b$ is equal to the number of points in $ u^\top x<b$ . Among all the hyperplanes that satisfy this constraint, we want to minimize over points that are in the space $ |u^\top x – b|\le \epsilon$ . Is there a relatively fast algorithm (quadratic or cubic at most) algorithm that solves this efficiently?

Ubuntu 18.04 Desktop installation using preseed freezing after partitioning

I’m trying to automate ubuntu 18.04 LTS Desktop installation using seed file, but unfortunately I’m unable to proceed futher after patitioning step while installation, as the window got hang.

Even I copy – paste entire “https://help.ubuntu.com/lts/installation-guide/example-preseed.txt” still the same problem

Below is the current configuration

d-i debian-installer/locale string en_US d-i passwd/user-fullname string test host d-i passwd/username string test d-i passwd/user-password password ubuntutest d-i passwd/user-password-again password ubuntutest d-i partman-auto/method string lvm d-i partman-lvm/device_remove_lvm boolean true d-i partman-lvm/confirm boolean true d-i partman-lvm/confirm_nooverwrite boolean true tasksel tasksel/first multiselect ubuntu-desktop d-i pkgsel/include string ssh vim build-essential   d-i pkgsel/upgrade select none 

I just mention the seed files in the boot params as auto url=http://192.168.56.101/test.cfg

Here I’m testing on Virtual box.

Please suggest

Partitioning a graph with specific constraints

We have an exercise where we need to find the partitions G[V1] and G[V2] of a graph G=(V,E), that fulfill the following constraints. We also know that there exists at least one partition that fulfills these constraints:

  • |V1| – |V2| = 0 or 1 (V1 and V2 have the same amount of nodes or V1 contains one node more that V2)
  • either
    • [case A] all nodes in V1 have edges to all nodes in V2
    • [case B] all nodes in V1 have no edges to any node in V2

We had a few ideas to find those partitions via divide-and-conquer involving the degrees of each node to differentiate between case A and B. If we find any node v with degree(v) < |V2| then there is a partition with case B, otherwise if we find a node v with degree(v) > |V1| then there is a partition that fulfills case A. However other than that we have been stuck and extendind or other ideas ended in a dead end.

How do we find those partitions? I’d like to not be given the answer but only a pointer to find a easy algorithm for the problem.

MongoDB replica set quorum config (network partitioning behaviour)

I use mongodb 4.0.10. I want to establish a quorum for a cluster of one primary node and two secondary nodes as written here. When the number of nodes is less than the quorum, 3 nodes in my case, cluster goes to readonly (no election).

I`ve tried to set priority of two nodes to 0, in this case if primary goes down, there is no election, but if one of secondaries goes down, old primary still exists.

According to MongoDB docs terminology is it possible to set a replica set Fault Tolerance to zero? It means that if any of cluster nodes goes down new primary will not be elected.

Octree for dense point cloud space partitioning

I am working on a project, trying to register point clouds extracted from consecutive video frames (rgb & depth images). The goal of this project is to align the point clouds of several frames, remove duplicate points and finally reconstruct the scene. The technology I decided to use is opengl which may or may not be ideal for this type of problem but is the one I am the most familiar with.

The dataset I am using consists of 2 640 x 480 images per frame, a 3 channel rgb image and a grayscale depth image. So far, I have successfully converted these to 3D point clouds. The next step is to try and register 2 point clouds taken from consecutive video frames, by implementing the iterative closest point algorithm (ICP) and using singular value decomposition to obtain the rigid transformation that aligns the point clouds optimally for each step of the algorithm.

In order to achieve a viable nearest neighbor search time I must use an appropriate data structure. My 2 options were kd-tree and octree and I decided on the octree since kd-tree requires sorting to find the median and the amount of points in each cloud is large 640 x 480 for a total of 307200 points.

The basic structure of the octree is as follows:

class octnode { public:     octnode(float xn, float xm, float yn, float ym, float zn, float zm, int l, octnode *par);     ~octnode();      float xmin;     float xmax;     float ymin;     float ymax;     float zmin;     float zmax;     int level;     bool isLeaf;     octnode *parent;      octnode* expand(glm::vec3 p);     bool contains(glm::vec3 p);     void addItem(int index);     void setChildren(octnode *a = NULL, octnode *b = NULL, octnode *c = NULL, octnode *d = NULL,     octnode *e = NULL, octnode *f = NULL, octnode *g = NULL, octnode *h = NULL);     octnode** getChildren();     glm::vec3 getCentroid();  private:     octnode **children;     glm::vec3 centroid;     std::vector<int> items; };    class octree { public:     octree(float minX, float maxX, float minY, float maxY, float minZ, float maxZ, int partitions);     ~octree();     void construct(octnode *root, int partitions);     void addItem(glm::vec3 p, int index);     std::vector<int> getSearchCandidates(glm::vec3 p);     void destroy(octnode *n);     void propagateItems(octnode *n, GLfloat *arr);     std::vector<octnode *> leaves; private:     octnode * root;     int depth;  }; 

The important methods that are used to create the tree are construct and propagateItems

void octree::construct(octnode *root, int partitions){  if (partitions == 0) {     leaves.push_back(root);     root->setChildren();     return; }  float xmin, xmax, ymin, ymax, zmin, zmax;  /* *       ROOT: *     E________________F *     /               /| *    /               / | *  A/_____________B_/  | *   |       |      |   | *   |       |      |   | *  G|_______|______|   |H *   |       |      |  / *   |       |      | / *  C|_______|_____D|/ * *   +x -> right *   +y -> top *   +z -> towards the screen */   //A xmin = root->xmin; xmax = (root->xmax + root->xmin) / 2; ymin = (root->ymax + root->ymin) / 2; ymax = root->ymax; zmin = root->zmin; zmax = (root->zmin + root->zmax) / 2;  octnode* chA = new octnode(xmin, xmax, ymin, ymax, zmin, zmax, root->level + 1, root); construct(chA, partitions - 1);  //B xmin = (root->xmin + root->xmax)/2; xmax = root->xmax; ymin = (root->ymax + root->ymin) / 2; ymax = root->ymax; zmin = root->zmin; zmax = (root->zmin + root->zmax) / 2;  octnode* chB = new octnode(xmin, xmax, ymin, ymax, zmin, zmax, root->level + 1, root); construct(chB, partitions - 1);  ...  root->setChildren(chA, chB, chC, chD, chE, chF, chG, chH); }    void octree::propagateItems(octnode * n, GLfloat *arr){  octnode** children = n->getChildren();  if (children[0] == NULL) {     cout << "propagation attempted on null children." << endl; }  //propagating each item to one of 8 children of this node for (int i = 0; i < n->getItems().size(); i++) {     //acquiring index from the array     int index = n->getItems().at(i);     //creating the appropriate vec3 object     glm::vec3 p(arr[3*index], arr[3*index + 1], arr[3*index + 2]);     //checking which child it matches     for (int k = 0; k < 8; k++) {         if (children[k]->contains(p)) {             children[k]->addItem(index);             break;         }     } }  //after propagating the items delete the "items" vector //from the current node. n->deleteItems(); } 

The idea is that once I obtain the bounding box of the point cloud, I then split it into 8 smaller equal boxes which are then split again until the proper number of partitions is reached. This would create a balanced octree. The “dense” aspect of the point cloud mentioned in the title comes from the fact that there are certain areas where the points are very close to each other. In these areas, when I created the octree, most of the nodes would have ~0 - 200 points (items) each and one node woud have 95000 points, making the nearest neighbor search impractical.

To solve that problem I decided to do more partitions in the nodes that had more items than a specified threshold:

int partitions = 5; int threshold = 1000;  //-> Creating only a single layer (8 leaf nodes) tree = new octree(minX-0.001, maxX+0.001, minY-0.001, maxY+0.001, minZ-0.001, maxZ+0.001, 1);  //-> Adding the items for (int i = 0; i < height; i++) {     for (int j = 0; j < width; j++) {         int index = i * width + j;         glm::vec3 p(vertexData[3 * index], vertexData[3 * index + 1], vertexData[3 * index + 2]);         tree->addItem(p, index);     } }  //-> Keep expanding the leaf nodes till the number of //items in each leaf node drops below a threshold bool done = false; std::vector<octnode *> leavesCopy = tree->leaves;  while (!done) {      done = true;     int sz = leavesCopy.size();      for (int i = 0; i < sz; i++) {         octnode *currentLeaf = leavesCopy.at(i);          //for each node whose items exceed the threshold         if (currentLeaf->getItems().size() > threshold) {             //create another layer below it             tree->construct(currentLeaf, 1);             //propagate its items to the new children             tree->propagateItems(currentLeaf, vertexData);             //if even a single leaf has been expanded, repeat the while             //loop again until no changes are to be made.             done = false;             //adding the newly created children to the array             std::vector<octnode *> ns = currentLeaf->getChildrenAsVector();             leavesCopy.insert(                 leavesCopy.end(),                 std::make_move_iterator(ns.begin()),                 std::make_move_iterator(ns.end())             );         }         else {             leavesCopy.push_back(currentLeaf);         }     }       //reconstructing the leaves array     leavesCopy.erase(leavesCopy.begin(), leavesCopy.begin() + sz); } 

Basically, I create an initial layer of 8 children and add the points to their corresponding child. After that every child is checked, and if it is found to have more items than the threshold allows, another layer is created and the items are propagated to that layer.

The problem is that this process takes approximately 6 minutes to finish for 1 point cloud, and I need 12 minutes to load 2 point clouds and try to align them. The aligning has several bugs in it which are really hard to find due to the large number of points available. I’ve already written more code than I can handle and the amount of time it takes to try to debug the application (>12 minutes) has become overwhelming.

Is there any way I could optimize the code to run faster? Am I even taking the right approach? I omitted some parts of the code, but I will include them if asked. Please forgive the long post and my inexperience on the subject.

Partitioning Scheme x Ubuntu

I’m trying to figure out how the minimun partition scheme requiring when i use BIOS or UEFI, MBR or GPT…..and LVM together because i’m really confused. Below i put the Simplest partition scheme combining together MBR,GPT UEFI and LVM Could you tell me if what i wrote is correct?

BIOS+MBR

1 swap 2 /

BIOS + GPT

1 Bios-grub 2 swap 3 /

UEFI + GPT

1 EFI boot partition 2 swap 3 /

BIOS + LVM i need to set /boot as Standard Partitions to make the linux bootable

1 /boot as standard Partition 2 swap LVM storage 3 / LV Storage

for BIOS with GPT Disk plus LVM? i need just to add the bios-grub partition(to support GPT disk) and the separated standard partition /boot to let linux to boot?

1 Bios-grub 2 /boot 3 swap LVM Storage 4 / LVM Storage

UEFI + LVM? just add the EFI partition to support UEFI and /boot standard partittion to let linux to boot or not?

1 efi 2 /boot 3 swap LVM Storage 4 / LVM Storage

Any clarification would be great……Tanks in advance

Partitioning a boolean circuit for automatic parallelization

tl;dr: I have a problem where I have a Boolean circuit and need to implement it with very specific single-thread primitives, such that SIMD computation is significantly cheaper after a threshold. I’m trying to optimize the implementation.

Going into detail, the input is a combinatorial Boolean circuit (so no loops, state, etc.). I’m implementing it in software with a rather unusual set of primitives, such that:

  • logic gates must be computed one at a time, as the “engine” is single-threaded
  • NOT gates are free
  • AND, OR, XOR have a cost of 1 (eg. 1 second)
  • N identical gates can be evaluated at the same time for a cost of 10 plus some tiny proportional term (eg. a batch of 20 distinct AND gates can be evaluated in 10 seconds, 50 distinct XOR gates in ~10 seconds, etc.)

The objective is to implement the circuit with the given primitives while minimizing the cost.


What I tried

This problem looks vaguely related to the bin packing problem, but the differences – constraints on the order of the items and different cost for each “bin” depending on the number of items – make me think it’s not particularly applicable.

I was suggested to use integer linear programming, which sounds like the best fit so far, but I’m not sure how to represent the problem. Specifically, I’d use binary variables to represent whether the implementation gate/batch M is used in place of the circuit gate N, but then I don’t know how to express the objectives to be maximized/minimized.

Optimizing graph partitioning by connected components of generated subgraph

I’m trying to optimize a function in a process which is going to be run millions of times. The function is supposed to partition the vertices of a graph, which will be used to make a quotient graph. Theoretically, the process is:

  1. Input a graph, G
  2. For each vertex, v in G, we choose a random edge of v (the same edge can be chosen for two different vertices)
  3. We have a subgraph S, where we only use the edges chosen in (2)
  4. We partition our vertices by which connected component they are in

Initially, I simply created S in NetworkX, but found that the process of creating a proper graph was unnecessarily slow. So next, I tried to recreate the bare-bones of the process where I locally created an adjacency dictionary and used that with the NetworkX documentation for finding connected components. Finally, I found it fastest to simply have a dictionary of which connected component each vertex is in, yet still it seems a bit redundant, as for each edge chosen, I need to update the dictionary for the entire connected component.

My fastest version:

def sp3(G):     nodes = list(G.nodes)     P = []     dic = {}     for v in nodes:         dic[v] = frozenset([v])     for v in nodes:         nb = random.choice(list(G.neighbors(v)))         U = frozenset.union(dic[v],dic[nb])         for a in U:             dic[a] = U     for v in nodes:         P.append(dic[v])     P = list(set(P))     return P 

Slower version:

def sp1(G):     nodes = list(G.nodes)     dic = {v:set() for v in nodes}     for v in nodes:         nb = random.choice(list(G.neighbors(v)))         dic[v].add(nb)         dic[nb].add(v)     P = list(CCbfs(dic))     return P  def CCbfs(dic):     seen = set()     for v in dic.keys():         if v not in seen:             c = frozenset(bfs(dic, v))             yield c             seen.update(c)  def bfs(dic,n):     d = dic     seen = set()     nextlevel = {n}     while nextlevel:         thislevel = nextlevel         nextlevel = set()         for v in thislevel:             if v not in seen:                 yield v                 seen.add(v)                 nextlevel.update(d[v]) 

I’ve been using cProfile and got the following on a 2690 vertex, nearly maximal planar graph (in reality I’m working with ~600 vertex subgraphs of this graph, but for convenience I just ran it on the whole thing):

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)         1    0.000    0.000   99.996   99.996 {built-in method builtins.exec}         1    0.000    0.000   99.996   99.996 <string>:1(<module>)         1    1.083    1.083   99.996   99.996 Imp2.py:1201(SPit)      2500   12.531    0.005   52.974    0.021 Imp2.py:1108(sp1)      2500   22.591    0.009   45.939    0.018 Imp2.py:1085(sp3)  13450000    9.168    0.000   29.084    0.000 random.py:256(choice)  13450000   12.218    0.000   18.138    0.000 random.py:224(_randbelow)    768750    2.602    0.000   13.118    0.000 Imp2.py:149(CCbfs)   7491250    7.274    0.000    9.910    0.000 Imp2.py:156(bfs)  13450000    6.418    0.000    9.225    0.000 graph.py:1209(neighbors)      2500    6.728    0.003    6.728    0.003 Imp2.py:1110(<dictcomp>)  20988370    4.325    0.000    4.325    0.000 {method 'getrandbits' of '_random.Random' objects}   6725000    3.312    0.000    3.312    0.000 {method 'union' of 'frozenset' objects}  13455000    2.810    0.000    2.810    0.000 {built-in method builtins.iter}  20175000    2.541    0.000    2.541    0.000 {method 'add' of 'set' objects}   7491250    2.329    0.000    2.329    0.000 {method 'update' of 'set' objects}  13455000    1.780    0.000    1.780    0.000 {built-in method builtins.len}  13450000    1.595    0.000    1.595    0.000 {method 'bit_length' of 'int' objects}   6725000    0.640    0.000    0.640    0.000 {method 'append' of 'list' objects}      5000    0.029    0.000    0.041    0.000 graph.py:646(nodes)      5000    0.012    0.000    0.012    0.000 reportviews.py:167(__init__)      5000    0.006    0.000    0.009    0.000 reportviews.py:174(__iter__)      5000    0.003    0.000    0.006    0.000 reportviews.py:171(__len__)      2500    0.001    0.000    0.001    0.000 {method 'keys' of 'dict' objects}         1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects} 

It seems like I spend so much time just going through the for loops in sp3… is there some way to fix this? (Also, I’ve been told to check if there’s a faster implementation than random.choice when I’m using really small lists usually of size 6, give or take, so any insight on that is welcome.)

Edit: here’s something to test the code, in reality I’m using an adjacency matrix created from some text files but it’s really messy and this should mostly capture the properties

def SPit(m=25,n):     G = nx.grid_2d_graph(m,m)     i=0     while i<n:         x1 = sp1(G)         x3 = sp3(G)         i+=1