We consider a Stackelberg game in a network, where a leader minimizes the cost of interdicting arcs and a follower seeks the shortest distance between given origin and destination nodes under uncertain arc traveling cost. In particular, we consider a risk-averse leader, who aims to keep high probability that the follower’s traveling distance is longer … Read more
In this paper, we introduce an $O(nm)$ time algorithm to determine the minimum length directed cycle in a directed network with $n$ nodes and $m$ arcs and with no negative length directed cycles. This result improves upon the previous best time bound of $O(nm + n^2 \log\log n)$. Our algorithm first determines the cycle with … Read more
In this note, we extend the existing algorithms Extra and subgradient-push to a new algorithm ExtraPush for convex consensus optimization over a directed network. When the network is stationary, we propose a simplified algorithm called Normalized ExtraPush. These algorithms use a fixed step size like in Extra and accept the column-stochastic mixing matrices like in … Read more
We consider a class of fixed-charge transportation problems over graphs. We show that this problem is strongly NP-hard, but solvable in pseudo-polynomial time over trees using dynamic programming. We also show that the LP formulation associated to the dynamic program can be obtained from extended formulations of single-node flow polytopes. Given these results, we present … Read more
The flow refueling location problem (FRLP) locates $p$ stations in order to maximize the flow volume that can be accommodated in a road network respecting the range limitations of the vehicles. This paper introduces the charging station location problem with plug-in hybrid electric vehicles (CSLP-PHEV) as a generalization of the FRLP. We consider not only … Read more
The budgeted minimum cost flow problem (BMCF(K)) with unit upgrading costs extends the classical minimum cost flow problem by allowing to reduce the cost of at most K arcs. In this paper, we consider complexity and algorithms for the special case of an uncapacitated network with just one source. By a reduction from 3-SAT we … Read more
We study the minimum-concave-cost flow problem on a two-dimensional grid. We characterize the computational complexity of this problem based on the number of rows and columns of the grid, the number of different capacities over all arcs, and the location of sources and sinks. The concave cost over each arc is assumed to be evaluated … Read more
This paper points out the impact of opportunity cost of time (high discount rate or high rate of time preference, time-dependent profits, etc.) in designing real-world Steiner trees like electricity, gas, water, or telecommunications networks. We present the Steiner Tree Scheduling Problem which consists of finding a Steiner tree in an activity-on-arc graph that spans … Read more
Given an undirected graph, the Vertex Coloring Problem (VCP) consists of assigning a color to each vertex of the graph in such a way that two adjacent vertices do not share the same color and the total number of colors is minimized. DSATUR based Branch and Bound (DSATUR) is an effective exact algorithm for the … Read more
In this paper we consider a particular method of clustering for graphs, namely the modularity density maximization. We propose a hierarchical divisive heuristic which works by splitting recursively a cluster into two new clusters by maximizing the modularity density, and we derive four reformulations for the mathematical programming model used to obtain the optimal splitting. … Read more