# Tagged Questions

33 views

### Need help formulating a Traveling Salesman (Deliveryman) Variation

I am working with the following TSP variation: A deliveryman has to deliver orders of items to several different locations around a city. The orders are: ...
36 views

### k- maximally link disjoint paths and equations

This problem is NP-complete and also discussed to some extent in Graph problems which are NP-Complete on directed graphs but polynomial on undirected graphs from the level of my reading from various ...
51 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 ...
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$ ...
50 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 ...
49 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, ...
21 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 ...
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 ...
219 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 ...
57 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!
79 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 ...
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 ...