Some graph optimization problems with weights satisfying linear constraints

DOI10.1007/s10878-021-00754-wzbMath1485.90144OpenAlexW4256268268MaRDI QIDQ5918487

Kameng Nip, Zhen-bo Wang, Tianning Shi

Publication date: 14 February 2022

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-021-00754-w

zbMATH Keywords

computational complexitylinear programmingapproximation algorithmpolynomial-time algorithmgraph optimization

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Related Items

Balanced graph partitioning based on mixed 0-1 linear programming and iteration vertex relocation algorithm

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• Scheduling under linear constraints
• On the hardness of approximating minimum vertex cover
• Linear and nonlinear programming.
• Bin packing under linear constraints
• Knapsack with variable weights satisfying linear constraints
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• On the Complexity of Nonlinear Mixed-Integer Optimization
• The Design of Approximation Algorithms
• Assignment Problems
• Reducibility among Combinatorial Problems
• Fibonacci heaps and their uses in improved network optimization algorithms
• Paths, Trees, and Flowers
• Combinatorial optimization. Theory and algorithms.
• Related machine scheduling with machine speeds satisfying linear constraints