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

DOI10.1016/S0377-2217(02)00876-7zbMATH Open1045.90011OpenAlexW2056975114MaRDI QIDQ1428068FDOQ1428068

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Finding the Minimum-Cost Maximum Flow in a Series-Parallel Network
• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• Title not available (Why is that?)
• Title not available (Why is that?)

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)