On the minimum s - t cut problem with budget constraints
成果类型：
Article
署名作者：
Aissi, Hassene; Mahjoub, A. Ridha
署名单位：
Centre National de la Recherche Scientifique (CNRS); CNRS - Institute for Information Sciences & Technologies (INS2I); Universite PSL; Universite Paris-Dauphine; Kuwait University
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-023-01987-9
发表日期：
2024
页码：
421-442
关键词：
摘要：
We consider in this paper the budgeted minimum s - t cut problem. Suppose that we are given a directed graph G = (V, A) with two distinguished nodes s and t, k non-negative cost functions c(1),..., c(k) : A -> Z(+), and k - 1 budget bounds b(1),..., bk(-1). The goal is to find a s - t cut C satisfying the budget constraints c(h)(C) <= b(h), for h = 1,..., k-1, and whose cost c(k) (C) is minimum. In this paper we discuss the linear relaxation of the problem and introduce a strict partial ordering on its solutions. We give a necessary and sufficient condition for which it has an integral optimal minimal (with respect to this ordering) basic solution. We also show that recognizing whether this is the case is NP-hard.
来源URL：