All Questions
Tagged with convex-optimization graph-theory
10 questions
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
1
vote
0
answers
79
views
Touring a sequence of convex polygons with minimal energy
There is a known problem of touring a sequence of $n$ polygons: given a starting point $s$, an ending point $t$ and a sequence of polygons $P_1,\dots,P_k$ with a total of $n$ vertices, find points $...
- 177
1
vote
0
answers
97
views
How to solve the following optimization problem?
Let $G=(V,E)$ be a connected network with $|V|=n$. Consider the following optimization problem
I'm trying to know under which conditions the following minimization problem has solution :
$${\sum _{i=1}...
- 47
4
votes
2
answers
243
views
Clustering of vertices in an $n$-dimensional cube
Consider the vertices of an $n$-dimensional cube. The distance between two vertices is measured as the minimum number of edges between the two vertices. Now consider a subset of these vertices.
If we ...
- 41
9
votes
2
answers
1k
views
Orthogonal representations of graphs
A faithful orthonormal representation of a graph $G=(V,E)$ on $n$ vertices $\{1,2,\dotsc,n\}$ is an assignment of unit vectors $v_1,v_2,...,v_n \in \mathbb{R}^d$ to the vertices of $G$ such that $\...
- 201
3
votes
1
answer
773
views
Is there some quantitative version of interlacing of eigenvalues of a matrix under rank-1 update?
Given a real symmetric matrix $A$ and a vector $v$ of the same dimension we know that the eigenvalues of $A + vv^T$ are left interlaced by the eigenvalues of $A$.
But do we have any quantitative ...
- 1,893
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
2
votes
1
answer
331
views
Reverse optimization of a minimum cost flow network
Given an undirected graph $(V,E)$, with $W$ as the weight of each edge, and a convex cost function $F(X)$, such as $|X|^k$ ($k>1$).
The cost to send $x$ unit of flow through edge $e_i$ is defined ...
- 21
1
vote
1
answer
277
views
Maximum Dispersion of a Connected Geometric Graph
Let $\left\{\mathbf{p}_1,\dots, \mathbf{p}_k\right\}$ be a set of points in $n$-dimensional Euclidean space, and let the second moment of these points be defined as:
$
U=\sum \limits_{i=1}^{k} ||\...
- 115
2
votes
0
answers
168
views
Recovering a partition from spectral properties of the graph Laplacian
Let $G$ be a weighted graph with vertices $V$. Let $W$ be its real-valued, non-negative, $|V|\times|V|$ adjacency/affinity matrix. Let $L = \mathrm{diag}(W\mathbf1)-W$ be the (unnormalized) graph ...