Bi-objective matchings with the triangle inequality

DOI10.1016/J.TCS.2017.01.012zbMATH Open1358.05230OpenAlexW2579614863MaRDI QIDQ515541FDOQ515541

Authors Laurent Gourvès, Fanny Pascual, Daniel Vanderpooten, Jérôme Monnot 

Publication date 16 March 2017

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://hal.sorbonne-universite.fr/hal-01488424/file/bimatchfinal.pdf

zbMATH Keywords

matchingapproximation algorithmbi-objective optimization

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Bi-criteria and approximation algorithms for restricted matchings
• Optimizing over a slice of the bipartite matching polytope
• Optimum matchings in weighted bipartite graphs
• Biobjective optimization problems on matroids with binary costs
• Constrained matching problems in bipartite graphs
• Approximation algorithms for bipartite matching with metric and geometric costs
• The triangle splitting method for biobjective mixed integer programming
• A polyhedral approach for a constrained matching problem
• Heuristic matching for graphs satisfying the triangle inequality

Cites Work

• scientific article; zbMATH DE number 4070651 (Why is no real title available?)
• scientific article; zbMATH DE number 2119733 (Why is no real title available?)
• scientific article; zbMATH DE number 915988 (Why is no real title available?)
• A note on scheduling to meet two min-sum objectives
• Approximate tradeoffs on weighted labeled matroids
• Approximation Schemes for the Restricted Shortest Path Problem
• Approximation algorithms for the bi-criteria weighted MAX-CUT problem
• Approximation with a fixed number of solutions of some multiobjective maximization problems
• Budgeted matching and budgeted matroid intersection via the gasoline puzzle
• Deterministic algorithms for multi-criteria max-TSP
• Many birds with one stone
• Multicriteria Optimization
• New approaches to multi-objective optimization
• On approximating multicriteria \textsc{TSP}
• On the existence of schedules that are near-optimal for both makespan and total weighted completion time
• Single approximation for the biobjective Max TSP
• Two phase algorithms for the bi-objective assignment problem

This page was built for publication: Bi-objective matchings with the triangle inequality

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