Narrow Results

An inverse optimization problem is defined as follows. Let S denote the set of feasible solutions of an optimization problem P, let c be a specified cost (capacity) vector, and x⁰ ∈ S. We want to perturb the cost (capacity) vector c to d so that x⁰ is an optimal solution of P with respect to the cost (capacity) vector d, and to minimize some objective function. In this paper, we consider the weighted inverse minimum cut problem under the bottleneck type Hamming distance. For the general case, we present a combinatorial algorithm that runs in strongly polynomial time.

This paper addresses a network optimization interdiction problem, called the maximum capacity path interdiction problem. The problem is a hierarchical game containing two players: one evader and one interdictor. In a capacitated network, the evader wants to find a simple path from his current position to a target point with maximum capacity to send his forces along it while the interdictor decreases arc capacities under a budget constraint to interdict the advance of the evader’s forces as much as possible. This paper studies the case that each arc has a fixed cost for decreasing its capacity. An algorithm is proposed to solve the problem in strongly polynomial time. Computational experiments on two real-world datasets guarantee the efficiency and accuracy of the algorithm.

Suppose that $G=(V,E)$ is an undirected graph. An ordered pair $(s,t)$ of the vertices of the graph $G$ is called a pendant pair for the graph if $\{t\}$ is a minimum cut separating $s$ and $t.$ Stoer and Wagner obtained a global minimum cut of $G$ by using pendant pairs of $G$ and its contractions. A Gomory Hu tree of the graph $G$ is a very useful data structure which gives us all the minimum s-t cuts of $G$ for every pair of distinct vertices $s$ and $t.$ In this paper, we construct a new type of tree for the graph $G,$ called cut star, by using pendant pairs of $G$ and its contractions. A cut star of the graph $G$ is constructed more quickly than a Gomory Hu tree of $G.$ We characterize a class of graphs for which a cut star of a graph of this class is also a Gomory Hu tree.

In this paper, we introduce a new algorithm for image texture synthesis from an input sample. In our approach, patch regions from a sample image are selected and copied to the output and then stitched together along optimal seams to generate a new output. In contrast to other techniques, we use min-cut/max-flow technique to determine the optimal patch region between the input and the output texture, and we use a zigzagged double direction scanning method instead of raster scan order method. This can restrain texel's imperfection and orientation of texture synthesis effectively. The results show that our method can produce a more satisfactory effect.