𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A cost-scaling algorithm for 0–1 submodular flows

✍ Scribed by Maiko Shigeno; Satoru Iwata

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
820 KB
Volume
73
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

✦ Synopsis

This paper presents a cost-scaling algorithm for minimum cost O-l submodular flows. The algorithm works by splitting the arc costs approximately and maintaining an optimal submodular pseudoflow with respect to the split costs obtained by a greedy algorithm. Each scaling phase of the algorithm is a hybrid version of an auction-like method with cost-splitting and a successiveshortest-path method, as a generalization of Orlin and Ahuja's algorithm for the assignment problem.

📜 SIMILAR VOLUMES

An approximation algorithm for quadratic
An approximation algorithm for quadratic cost 0–1 mixed integer programming problems
✍ Kumiko Mukai; Keiji Tatsumi; Masao Fukushima 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 586 KB

In this paper, we focus on the quadratic cost 01 mixed integer programming problem. First, we formulate the problem as a two-level programming problem that consists of a lower-level continuous quadratic programming problem with 01 variables fixed and an upper-level nonlinear 01 programming problem.

A capacity scaling algorithm for the con
A capacity scaling algorithm for the constrained maximum flow problem
✍ Ravindra K. Ahuja; James B. Orlin 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 970 KB

## Abstract The constrained maximum flow problem is to send the maximum possible flow from a source node s to a sink node t in a directed network subject to a budget constraint that the cost of flow is no more than __D__. In this paper, we consider two versions of this problem: (i) when the cost of