Tag: minimum

Minimum spanning tree formulation

Can any expert explain the reasoning behind the constraint in the following formulation of the minimum spanning tree?

To formulate the minimum-cost spanning tree (MST) problem as an LP, we associate a variable $ x_e$ with every edge $ e \in E$ . Each spanning tree $ T$ corresponds to its incidence vector $ x^T$ , which is defined by $ x^T_e = 1$ if $ T$ contains $ e$ and $ x^T_e = 0$ otherwise. Let $ \Pi$ denote the set of all partitions of the vertex set $ V$ , and suppose that $ \pi \in \Pi$ . The rank $ r(\pi)$ of $ \pi$ is the number of parts of $ \pi$ . Let $ E_\pi$ denote the set of edges whose ends lie in different parts of $ \pi$ . Consider the following LP: $ $ \begin{align*} \min &\sum_{e \in E} c_ex_e \ \text{s.t. } &\sum_{e \in E_\pi} x_e \geq r(\pi) – 1 \quad \forall \pi \in \Pi, \ & x \geq 0. \ \end{align*} $ $

Minimum number of swaps in sorting sequence

Given an array of N integer elements (not necessarily distinct), what is the minimum number of swaps (not necessarily adjacent) needed to sort the array?

I’ve been struggling with this problem for a few months now. I know that the elements are distinct, the answer is the number of cycles in the permutation obtained after normalizing the values and that if the swaps are adjacent bubble sort obtains the optimum number of swaps, but nothing about this one. This question asks the same, but the answers only consider distinct elements.

My approach to the problem is graph theoretical, considering a graph with a node for each element value, drawing an oriented edge from $ a$ to $ b$ whenever a value $ a$ lies at a position where $ b$ should lie in the sorted array ($ a \neq b$ , so no loops), the answer being the maximal (partition with most equivalence classes) partition of the edges into simple cycles (a generalization of the solution for arrays with distinct elements).

Does this problem have a known name? Any references? Any polynomial solution or complexity class ownership (P, NP, graph isomorphism equivalence etc)?

Is there a data structure that can perform range modulo additions and range minimum queries?

It is well-known that the Segment Tree performs range additions and range minimum queries in O(logN) each.

Let each element in the array have value V[i], M[i]. We define a “range modulo add” as the following: add +X to V[i] for each element in the range L<=i<=R and then calculate modulo M[i] for each element L<=i<=R. Can both this operation and range minimum queries be run in (worst-case or average-case) o(N)? If not on ranges [L,R], is it possible to handle range minimum queries and range modulo adds on the entire array quickly?

0-1 knapsack problem with minimum and maximum weight capacity

In classical 0-1 knapsack problem we have maximum allowed value for the weight – weight capacity.

Let’s restrict total knapsack weight by min and max values

$ $ M \leq \sum_{i=1}^{n}{w_i x_i} \leq W $ $

Is there any known algorithm for this problem? Is there anything known which is better than brute force?

I failed to find anything about the given knapsack problem variation.

Finding Minimum Weight Subgraph with k Vertices

Assume a complete graph G={V,E} that has n vertices and $ C_{n}^{2}$ edges, and the weights of E are all positive. I am trying to find a complete subgraph containing k vertices, and it has the maximum sum of edge weights among all the complete subgraph with k vertices. My question is, other than the brutal force method that needs to traverse all posible subgraph with k vertices ($ C_{n}^{k}$ ), is there an algorithm that is faster than the brutal force, or has polynomial complexity?

Schedule a Seminar in Minimum Time

There are t1, t2, t3,…..,tn topics which are to be scheduled in a building with c1,c2,c3,….ck halls. Members have already registered there interests on the topics, and they have liberty to choose any number of topics. There will be only one session on a given day per hall.

The problem is to finish the seminar in minimum time with least members missing on their topics.

My Solution:

For strictly no one missing on the topics there can be only one session on a day in only one hall and rest halls to be left unused. This takes longest possible time to finish the event. Only when all the k halls are utilized simultaneously, we can do it fastest.

Lets assume that ti is the set of all members interested in the i-th topic.

I am looking at a brute force solution in which we observe combinations of k topics (one topic per hall) to be scheduled at once. The effort is to find out intersection of groups in which cardinality of set with members choosing all those k-topics is minimum. Initially, there are nCk combinations, and after we schedule the first k-topics we can look for next n-kCk and then n-2kCk, n-3kCk… topics and so on.

As we see here, the main effort here is to find the intersection of k-sets. To me it looks like there should be some dynamic programming mechanism to reduce the repeated effort which I am unable to figure out. Do we have some thing absolutely different?

It is not a homework.

Auto-Shrinking All Databases Files To Their Minimum Size In Sql Server

I restore my all databases in production to my development environment monthly. Development server has 4 TB disk space and there are 4 different instances over it which containt databases on the production server. In Development, i can truncate and shrink some big-sized tables to expand free disk space. The purpose of doing this process is the complaint of software developers about the development server slowness. I talked to system administrator team and they informed me that the slowness was because of the insufficient disk space area. So, i make this work. My question is about how i can shrink all database files to their minimum size after truncating related tables. So, should i make it with powershell, and how?

Network Flow – Minimum flow in a network

I have a directed graph G=(V,E) with a source s$ \in V$ and a sink t$ \in V$ . There is a minimum capacity (lower bound) l $ _{e}$ for each edge in G. There are no upper bounds on the edges.

In a course that I took, the professor told that to find a minimum flow –

1) We need to assign a large capacity to all edges and find flow f
2) Construct G $ _{1}$ where all edges are reversed and each edge has capacity f$ _{e}$ – l$ _{e}$
3) We need to then find the max flow from t to s in G$ _{1}$ that is f$ _{1}$
4) Then, the minimum flow in G is f-f$ _{1}$

My question is- Why can’t we find a s to t path in G with the least value of l$ _{e}$ . The least value of l$ _{e}$ would be the minimum flow that could be pushed through the network?

Graph of size n with girth >2k and minimum degree more than n^1/k

I’m stuck at a proof about Graphs in the context of Graph Spanners. A Lemma says:
Let $ G$ be a graph with $ n$ vertices and $ m$ edges. If $ G$ has girth more than $ 2k$ , then $ m\leq n^{1+\frac{1}{k}}$ .
The proof is made by contradiction where repeatedly any node from $ G$ of degree at most $ \lceil n^\frac{1}{k}\rceil$ and any edges incident to that node is removed, until there is no such node anymore. This step leads to a subgraph $ G’$ of $ G$ of minimum degree more than $ \lceil n^\frac{1}{k}\rceil$ .
The conclusion is that $ G’$ must have girth at most $ 2k$ and therefore also $ G$ , which is a contradiction.

I don’t understand the conclusion: Why must $ G’$ have girth at most $ 2k$ ? Why is it not possible that $ G$ has girth more than $ 2k$ and minimum degree more than $ \lceil n^\frac{1}{k}\rceil$ ?

I don’t really see an answer to this question, so I would be very grateful if someone can help me.