Approximate Inference in Logical Credal Networks
Radu Marinescu, Haifeng Qian, et al.
IJCAI 2023
Given a graph where increasing the weight of an edge has a nondecreasing convex piecewise linear cost, we study the problem of finding a minimum cost increase of the weights so that the value of all minimum spanning trees is equal to some target value. Frederickson and Solis-Oba gave an algorithm for the case when the costs are linear. We give a different derivation of their algorithm, and we slightly extend it to deal with convex piecewise linear costs. We formulate the problem as a combinatorial linear program and show how to produce primal and dual solutions. © 2008 Wiley Periodicals, Inc.
Radu Marinescu, Haifeng Qian, et al.
IJCAI 2023
Marcos Goycoolea, Alan T. Murray, et al.
Operations Research
Mourad Baïou, Francisco Barahona, et al.
Electron. Notes Discrete Math.
Mourad Baiou, Francisco Barahona
Mathematical Programming