Inapproximability and a polynomially solvable special case of a network improvement problem.

DOI10.1016/S0377-2217(02)00876-7MaRDI QIDQ1428068zbMATH OpenOpenAlexFDO

Authors Jianzhong Zhang, Xiaoguang Yang, Mao-Cheng Cai

Publication date 14 March 2004

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0377-2217(02)00876-7

zbMATH Keywords

Shortest pathInapproximabilityNetwork flowsMaximum 3-satisfiability

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• A network improvement problem under different norms
• The complexity analysis of the shortest path improvement problem under the Hamming distance
• scientific article; zbMATH DE number 1487883
• Approximation algorithms for certain network improvement problems
• On the approximability of some network design problems

Cites work

• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• scientific article; zbMATH DE number 1086909 (Why is no real title available?)
• scientific article; zbMATH DE number 1522936 (Why is no real title available?)
• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• Finding the Minimum-Cost Maximum Flow in a Series-Parallel Network
• Network flows. Theory, algorithms, and applications.

Cited in

(8)

• The inverse 1-median problem on tree networks with variable real edge lengths
• A network improvement problem under different norms
• Combinatorial network abstraction by trees and distances
• The inverse 1-maxian problem with edge length modification
• Improved algorithms for the multicut and multiflow problems in rooted trees
• Reverse 2-median problem on trees
• Up- and downgrading the 1-center in a network
• Complexity of some inverse shortest path lengths problems

This page was built for publication: Inapproximability and a polynomially solvable special case of a network improvement problem.

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