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

DOI10.1016/J.DAM.2006.02.008MaRDI QIDQ2499589zbMATH OpenOpenAlexFDO

Authors Eric Angel, Evripidis Bampis, Laurent Gourvès

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 algorithmbicriteria MAX-CUT problemmulticriteria optimizationperformance guarantee

Mathematics Subject Classification ID

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

Recommendations

• Graph-Theoretic Concepts in Computer Science
• Improved approximation algorithms for MAX k-cut and MAX BISECTION
• Improved approximation algorithms for MAX k-CUT and MAX BISECTION
• Approximation algorithms for maximum cut with limited unbalance
• Approximating Maximum Cut with Limited Unbalance

Cites work

• A note on scheduling to meet two min-sum objectives
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
• Bicriteria approximation algorithms for scheduling problems with communications delays
• Cardinality constrained minimum cut problems: complexity and algorithms.
• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• scientific article; zbMATH DE number 1305482 (Why is no real title available?)
• scientific article; zbMATH DE number 2119733 (Why is no real title available?)
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Multicriteria optimization
• On the existence of schedules that are near-optimal for both makespan and total weighted completion time

Cited in

(10)

• Approximation schemes for bi-objective combinatorial optimization and their application to the TSP with profits
• Simultaneous approximation of constraint satisfaction problems
• Approximation with a fixed number of solutions of some multiobjective maximization problems
• Simultaneous approximation of multi-criteria submodular function maximization
• Approximation Methods for Multiobjective Optimization Problems: A Survey
• Covers and approximations in multiobjective optimization
• Bi-objective matchings with the triangle inequality
• Graph-Theoretic Concepts in Computer Science
• Generalized Nash fairness solutions for bi-objective discrete optimization: theory and algorithms
• Fault tolerant max-cut

Describes a project that uses

Uses Software

• TSPLIB

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

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