1
vote
0answers
48 views

Formula for position in an upper triangular matrix

I'm currently working on the Travelling Salesman's Problem in a computer science module. I have implemented some linear programming techniques using the software lp_solve. I've ended up with an upper ...
0
votes
1answer
72 views

A question about rational number.

Denote $M$ as a $m\times n$ matrix whose components are all nonnegative integers (actually 0 or 1) and $1$ as the $m$ dimensional vector $(1,1,\cdots,1)$. Show that: There is a vector $x_0$ ...
0
votes
1answer
46 views

Min-Cost-Flow Problem

Given a directed graph $G = (V,E)$ with a cost function $\gamma: E \to \Bbb R_{\geq 0}$ and two vertices $u,v \in V$. How to reduce the problem of finding a directed path from $u$ to $v$ with minimum ...
0
votes
0answers
44 views

Model a shortest path linear programming problem

I have a graph with 8 vertex, and i'm supposed to model a linear programming problem which consists in delivering 10 trash containers (1 is in vertex 1, 3 are at vertex 2, 2 are located at vertex 5, ...
0
votes
0answers
17 views

Generalization of size reduction of Linear Assignment Problems

It is well known, that the LAP has super linear complexity. Hence, problem-size reduction is a viable optimization strategy. For instance, if one task is incident to exactly two workers, one can ...
1
vote
1answer
38 views

Constrained Minimization Problem derived from a Directed Graph

I'm looking for a solution the following graph problem for data analysis purposes. Basically, I have a directed graph of $N$ nodes where I know the following: The sum of the weights of the ...
2
votes
1answer
163 views

comparison of simplex and shortest path method

In mathematical optimization, Dantzig's simplex algorithm (or simplex method) is a popular algorithm for linear programming. The journal Computing in Science and Engineering listed it as one of the ...
1
vote
0answers
55 views

computing dual LP in graph matchings

I'm having a trouble converting the following LP to a dual LP. Help on some starting steps would be greatly appreciated!
0
votes
0answers
73 views

Maximum matching in a non-bipartite graph

The problem is the following; I would like to reach maximum matching in a 2-connected graph, but not in an ordinary way - both of the groups of vertices that we get after the matching should remain ...
3
votes
0answers
167 views

The size of the maximum matching is bounded by the size of the minimum vertex cover

Prove, using the weak duality theorem of linear programming, that: For any graph $G$ (not necessarily bipartite), the size of the maximum matching is at most the size of the minimum vertex ...
0
votes
0answers
171 views

Its just one point… How do I find it?

Okay so here is the deal... I have a CLOSED convex polyhedron $Ax \le b$ (where $x$ is in $R^n$) and it has i vertices denoted $V_i$ such that $V_i = (x_{i1}, x_{i2}, \ldots, x_{iN})$ where $0 \le ...
0
votes
1answer
187 views

Different formulation of a Traveling Salesman Problem

Given a undirected, weighted, complete graph $(V,E,c)$ with $c \to \mathbb{N}$ and $v_0 \in V$ we are looking for a set $E' \subset E$ minimal with respect to $c$ with the following conditions: for ...
6
votes
1answer
320 views

What is graph theory interpretation of this linear programming problem?

So, I am looking at a paper by Rosenfeld, "On a problem of C.E. Shannon in graph theory", where he gives necessary and sufficient conditions for a graph $H$ to satisfy $$\alpha(G \boxtimes H) = ...
3
votes
4answers
471 views

Finding minimal cost edge cover for a bipartie graph

I have got two sets of elements and a pruned graph of bipartie edges with weights assigned to each edge. I need to find the minimal set of edged with the minimum cost covering all nodes from both ...
3
votes
1answer
324 views

Connected graph solution from IP/LP

I have a problem on a graph (of maximum degree $c$) which looks for a connected subset of edges fulfilling some properties. I have problems formulating the connectedness condition in an IP/LP. The ...
4
votes
1answer
342 views

Linear programming for combinatorics/graph theory

I just went to a graph theory talk talking about various fractional graph parameters (but focusing on one). These were defined using linear programming. A question was asked, "How can we learn more ...
1
vote
0answers
153 views

l1-metric and cut metric equivalence

I would like to show that the following two statements are equivalent. Let (A, d) be an n-point metric space. And B set of $\binom{n}{2}$ pairs of points of A. $\exists t \geq 1$, integer m, and ...