All Questions
33 questions
10
votes
1
answer
411
views
Network flows with capacities on pairs of edges
Take a standard network flow problem: a directed graph with nonnegative capacities on each edge, a source $s$, a sink $t$. We all know how to find the maximum flow from $s$ to $t$.
Now add edge-pair ...
- 37.7k
10
votes
0
answers
722
views
Fractional Matching version of Hall's Marriage theorem
Let $G=(S,T,E)$ be a bipartite graph, $|S|=|T|$. Then the following are equivalent:
1) there exist a perfect matching in $G$;
2) there exist non-negative weights on edges such that the sum of ...
- 109k
9
votes
1
answer
295
views
Definition of packing property
Definition 1:
A clutter $C$ is said to have the packing property if $C$ and all of its minors satisfy the König property.
where,
vertex cover of $C$ is a set of vertices that have non-empty ...
- 381
7
votes
1
answer
386
views
Which zero-diagonal matrices contain the all-one vector in their columns' conic hull?
Let $A$ be a non-negative zero-diagonal invertible matrix. Which $A$ make the following assertions true, which are all equivalent:
The all-one vector $j$ is contained in the conic hull of $col(A)$.
...
- 81
5
votes
1
answer
183
views
Resource Constrained Routing with Refueling
What are good algorithms (resp. models) for calculating optimal or near optimal routes while taking into account fuel consumption, options for refueling and, limited tank capacity?
Especially modeling ...
- 13.2k
5
votes
1
answer
2k
views
Algorithm to minimally connect line segments in Euclidean plane
Suppose you have finitely many line segments in the Euclidean plane. How do you "connect them to form one chain of line segments of minimal length?"
More formally and generally, what I'm looking for ...
- 153
5
votes
0
answers
194
views
A linear optimization problem on a graph
Let $G=(V,E)$ be a finite graph and let $f$ be any positive function defined on the vertices. Put weights on the vertices $v_{i}$, way $w_{i}$ so that $\sum_{i=1}^{n}w_{i}\leq 1$. Assume that every ...
- 2,288
5
votes
0
answers
581
views
When is polytope compatible with network flow?
A linear program is the problem of optimizing an linear objective function within some polytope $A$ over $\mathbf R^n$. My question is motivated by the question of when a linear programming problem ...
- 3,475
4
votes
2
answers
315
views
Connecting $2n$ points in $\mathbb R^2$ with line segments s.t. each point belongs to exactly one line segment
I'm trying to do a certain simulation related to the toric code and I'm looking for an algorithm that connects $2n$ points ($n \in \mathbb Z_+$) in $\mathbb R^2$ with line segments with the following ...
- 269
4
votes
1
answer
966
views
Solving for Hamiltonian path with constraints on allowable routes through vertices
Suppose you have a complete graph with N vertexes, with a distinguished vertex $n=1$ ("start"), and you wish to find a route traveling exactly once through each vertex so that the distance along the ...
3
votes
2
answers
791
views
complexity of finding optimal matchings of given fixed size
It is known, that maximal matchings (i.e. matchings with the maximal number of edges) and optimal matchings (i.e. matchings for which the sum of edge weights is optimal) can be calculated in ...
- 13.2k
3
votes
2
answers
1k
views
SDP relaxation vs LP relaxation
I have a question I hope you might be able to answer.
Let's say we have an integer program for the stable set problem (or clique, not principal).
\begin{equation}
\begin{aligned}
& \text{...
- 342
2
votes
4
answers
212
views
Efficient algorithm for graph problem
Let $D=(V,E)$ be a directed graph, $S,T\subset V$ and $f:V\rightarrow \{1,\ldots, k\}$ a positive, bounded weight-function and $l\in \mathbb{N}$, find a path $v_1,\ldots, v_l\in V$ with $v_1\in S$ and ...
- 157
2
votes
1
answer
1k
views
What does the basis of the null space of the constraint matrix of a flow problem look like?
Consider a directed graph $G=(V,\mathbb{A})$ and a set of flow constraints of the following form:
$$ \sum_{(u,v)\in\mathbb{A}}x_{u,v} - \sum_{(v,u)\in \mathbb{A}}x_{v,u} = 0 \forall v \in V$$
...
- 31
2
votes
1
answer
485
views
Odd cycle transversal
Suppose we have a graph G. Say B a fundamental basis of the cycle space of G. Say LP a linear programming problem where there is a variable for each vertex of G, each variable can take value $\geq 0$, ...
2
votes
1
answer
848
views
Algorithm for satisfiability of inequalities.
I am looking for an algorithm for checking the satisfiability (with natural values) of a set of inequalities made of variables and natural numbers, for example: $u < v, u \leq z, 3 \leq v$.
In ...
- 85
2
votes
1
answer
3k
views
max-flow at max-cost
I have a flow network with gains. In practical terms, a gain is the opposite of a cost. So, I interested in finding the maximal gain of a network flow, what could be interpreted as finding a maximum ...
- 121
2
votes
1
answer
426
views
Network flows with shared capacities
Suppose we have a flow network, with capacity constraints on weighted sums of arc flows, such as:
$$2 f(1, 2) + 3 f(4, 5) + f(3, 7) \leq 10,$$
where $f(1, 2)$ denotes the flow through arc $(1, 2)$....
- 23
2
votes
0
answers
126
views
Unveiling hidden structures
One way to unveil a hidden structure of a undirected graph - given as an adjacency matrix - is to permute the rows and columns until a pattern with a maximal geometrical symmetry is found. (The ...
- 9,720
2
votes
0
answers
177
views
Formulating shortest path as submodular minimization
I'm curious about the general question of whether any combinatorial optimization problem with polynomial time solution can necessarily be reformulated as minimizing a submodular function.
The answer ...
- 21
1
vote
1
answer
69
views
$A^*$ algorithm to find shortest path when weights in my graph are the inverse of distance
Given a graph G=(V,E) where the weights on my edges are inverse of Euclidian distance between nodes, I want to know if I can use A* algorithm to find the shortest path. How I need to modify the ...
- 111
1
vote
2
answers
958
views
Integer linear programming (ILP) formulation of connectivity of induced subgraph
Can anyone assist me to find out what should be the ILP formulation of a case when I try to label vertices by say $0$, $1$ and $2$ and want the subgraph of graph $(V,E)$ made by same vertex set but ...
1
vote
0
answers
62
views
LP Constraints for Bridgeless Cactus Graphs
When trying to determine the optimal bridgeless spanning cactus graph of a weighted, symmetric graph, I got stuck.
What I do not know how to capture, is
the variable number and sizes of the cycles
...
- 13.2k
1
vote
0
answers
60
views
On the defect of a flow network
This problem in graph theory was actually motivated by some problems in Theory of Fractals.
To formulate the problem I need to recall some definitions related to flow network.
A flow network is a ...
- 41.8k
1
vote
0
answers
20
views
Calculating Cost-Optimal 1-Factors in Digraphs
I need to find a cost-optimal 1-factor in a positively weighted, directed, regular graph $G(V,A)$ without antiparallel arcs, i.e. given $$\text{deg}_{\text{in}}(u)=\text{deg}_{\text{in}}(v)=\text{deg}...
- 13.2k
1
vote
0
answers
43
views
a question about probabilities on spaces of digraphs
Let $G$ be a directed graph with fixed nodes $s$ and $t$. Assume that each edge $e$ in the graph comes with a number $n(e)\in[0,1]$.
We consider probability spaces $S$ whose points are directed ...
- 61
1
vote
1
answer
219
views
approximate diameter of polytopes in high dimensions
I just came across the following problem:
Let us consider the unit corner of the n-cube
$$
\Delta^n = \left\{(t_1,\cdots,t_n)\in\mathbb{R}^n\mid\sum_{i = 1}^{n}{t_i} \leq 1 \mbox{ and } t_i \ge 0 \...
- 75
1
vote
1
answer
241
views
Covering max flow arcs by arc disjoint paths
Let $(N,A,s,t,u)$ be a network with node set $N$, arc set $A$, source $s\in N$, sink $t\in N$ and capacity vector $u\in\{1,2,\ldots,T\}^A$, and let $x=(x_a)_{a\in A}$ be a maximum $(s,t)$-flow. Is it ...
- 2,966
0
votes
1
answer
76
views
A question on graph partitioning
Given a connected un-directed simple graph $G=(V,E)$, is there a polynomial time algorithm to find the smallest subset $S$ of $V$ such that each node in $V \setminus S$ has at least 50% of its ...
- 1,216
0
votes
1
answer
2k
views
Find edge weights that fit given node weights
Let $G = (V,E)$ be a connected simple graph (unweighted, undirected, no selfloops) on $n$ nodes.
Let $\mathbf{d} := (d_1, d_2, ..., d_n) \in \mathbb{R}_{>0}^n$ be a vector of arbitrary given node ...
- 340
0
votes
0
answers
40
views
Subtour-gluing constraints for ILP formulation of TSPs
If one doesn't want to introduce additional variables to the ILP of a TSP instance, one has to add exponentially many so-called subtour-elimination constraints; in practical calculations subtour-...
- 13.2k
0
votes
0
answers
99
views
Is this Graph Iteration Already Known?
When attempting to set up an ILP formulation for a weight-minimal cubic spanning tree (i.e. one with vertex degrees either 1 or 3) I needed connectivity constraint, but misremembered the contents of ...
- 13.2k
0
votes
2
answers
102
views
Does Max Flow produce uniform results? [closed]
I am interested in using Max Flow algorithm. I want to simulate transfer of quantity. Anyway, I am unsure of some thing.
Does Max Flow algorithm produce uniformly distributed max flow?
I have ...
- 11