Approximation algorithms for the bi-criteria weighted MAX-CUT problem

DOI10.1016/j.dam.2006.02.008zbMath1110.68168OpenAlexW2002060450MaRDI QIDQ2499589

Laurent Gourvès, Evripidis Bampis, Eric Angel

Publication date: 14 August 2006

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2006.02.008

zbMATH Keywords

approximation algorithmmulticriteria optimizationperformance guaranteebicriteria MAX-CUT problem

Mathematics Subject Classification ID

Multi-objective and goal programming (90C29) Approximation algorithms (68W25)

Related Items (7)

Simultaneous Approximation of Constraint Satisfaction Problems ⋮ Approximation schemes for bi-objective combinatorial optimization and their application to the TSP with profits ⋮ Approximation Methods for Multiobjective Optimization Problems: A Survey ⋮ Approximation with a fixed number of solutions of some multiobjective maximization problems ⋮ Simultaneous approximation of multi-criteria submodular function maximization ⋮ Covers and approximations in multiobjective optimization ⋮ Bi-objective matchings with the triangle inequality

Uses Software

• TSPLIB

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Bicriteria approximation algorithms for scheduling problems with communications delays
• On the existence of schedules that are near-optimal for both makespan and total weighted completion time
• Cardinality constrained minimum cut problems: complexity and algorithms.
• Multicriteria optimization
• A note on scheduling to meet two min-sum objectives
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science

This page was built for publication: Approximation algorithms for the bi-criteria weighted MAX-CUT problem