Algorithm for constraint partial inverse matroid problem with weight increase forbidden

DOI10.1016/J.TCS.2016.06.002MaRDI QIDQ2629239zbMATH OpenOpenAlexFDO

Authors Shuangshuang Li, Zhao Zhang, Hong-Jian Lai

Publication date 5 July 2016

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2016.06.002

zbMATH Keywords

matroidpolynomial time algorithmweight constraintpartial inverse optimization problem

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Nonnumerical algorithms (68W05) Combinatorial aspects of matroids and geometric lattices (05B35)

Recommendations

• Algorithms for the partial inverse matroid problem in which weights can only be increased
• The partial inverse minimum spanning tree problem when weight increase is forbidden
• Inverse matroid optimization problem under the weighted Hamming distances
• A weighted linear matroid parity algorithm
• A weighted linear matroid parity algorithm
• Combinatorial algorithms for solving the restricted bounded inverse optimal value problem on minimum spanning tree under weighted \(l_\infty\) norm
• An algebraic algorithm for weighted linear matroid intersection
• On the inverse problem of linear programming and its application to minimum weight perfect \(k\)-matching
• scientific article; zbMATH DE number 1159475
• scientific article; zbMATH DE number 1559133

Cites work

• scientific article; zbMATH DE number 5823945 (Why is no real title available?)
• scientific article; zbMATH DE number 420868 (Why is no real title available?)
• Algorithms for the partial inverse matroid problem in which weights can only be increased
• Complexity of partial inverse assignment problem and partial inverse cut problem
• Inverse Optimization
• Inverse combinatorial optimization: a survey on problems, methods, and results
• Inverse sorting problem by minimizing the total weighted number of changes and partial inverse sorting problems
• Matroids and the greedy algorithm
• On an instance of the inverse shortest paths problem
• Partial inverse assignment problems under \(l_{1}\) norm
• The base-matroid and inverse combinatorial optimization problems.
• The partial inverse minimum cut problem with \(L_1\)-norm is strongly NP-hard
• The partial inverse minimum spanning tree problem when weight increase is forbidden

Cited in

(14)

• Capacitated inverse optimal value problem on minimum spanning tree under bottleneck Hamming distance
• Capacitated partial inverse maximum spanning tree under the weighted \(l_{\infty }\)-norm
• Capacitated partial inverse maximum spanning tree under the weighted Hamming distance
• Partial inverse min-max spanning tree problem under the weighted bottleneck Hamming distance
• Inverse optimal value problem on minimum spanning tree under unit \(l_{\infty}\) norm
• Inverse max+sum spanning tree problem under weighted \(l_{\infty}\) norm by modifying max-weight vector
• Approximation algorithms for capacitated partial inverse maximum spanning tree problem
• Combinatorial algorithms for restricted inverse optimal value problems on minimum spanning tree under weighted \(l_1\) norm
• The lower bounded inverse optimal value problem on minimum spanning tree under unit \(l_{\infty}\) norm
• Inverse optimization problems with multiple weight functions
• Partial inverse min-max spanning tree problem under the weighted bottleneck Hamming distance
• Algorithms for the partial inverse matroid problem in which weights can only be increased
• Partial inverse maximum spanning tree in which weight can only be decreased under \(l_p\)-norm
• Partial inverse maximum spanning tree problem under the Chebyshev norm

This page was built for publication: Algorithm for constraint partial inverse matroid problem with weight increase forbidden

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2629239)