Algorithm for constraint partial inverse matroid problem with weight increase forbidden

DOI10.1016/j.tcs.2016.06.002zbMath1345.05011OpenAlexW2436549743MaRDI QIDQ2629239

Shuangshuang Li, Hong-Jian Lai, Zhao Zhang

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

polynomial time algorithmmatroidweight constraintpartial inverse optimization problem

Mathematics Subject Classification ID

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

Related Items (12)

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

Cites Work

• Unnamed Item
• Unnamed Item
• Algorithms for the partial inverse matroid problem in which weights can only be increased
• Inverse sorting problem by minimizing the total weighted number of changes and partial inverse sorting problems
• On an instance of the inverse shortest paths problem
• The base-matroid and inverse combinatorial optimization problems.
• Inverse combinatorial optimization: a survey on problems, methods, and results
• The partial inverse minimum spanning tree problem when weight increase is forbidden
• Partial inverse assignment problems under \(l_{1}\) norm
• Complexity of Partial Inverse Assignment Problem and Partial Inverse Cut Problem
• The partial inverse minimum cut problem withL₁-norm is strongly NP-hard
• Inverse Optimization
• Matroids and the greedy algorithm

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