Applications of discrepancy theory in multiobjective approximation

DOI10.4230/LIPICS.FSTTCS.2011.55MaRDI QIDQ2911611zbMATH OpenOpenAlexFDO

Authors Christian Glaßer, Christian Reitwießner, Maximilian Witek

Publication date 31 August 2012

Full work available at URL https://arxiv.org/abs/1107.0634

zbMATH Keywords

multiobjective optimizationtraveling salesman problemsatisfiabilitydiscrepancy theory

Mathematics Subject Classification ID

Multi-objective and goal programming (90C29) Programming involving graphs or networks (90C35) Randomized algorithms (68W20) Approximation algorithms (68W25) Abstract computational complexity for mathematical programming problems (90C60)

Abstract: We apply a multi-color extension of the Beck-Fiala theorem to show that the multiobjective maximum traveling salesman problem is randomized 1/2-approximable on directed graphs and randomized 2/3-approximable on undirected graphs. Using the same technique we show that the multiobjective maximum satisfiablilty problem is 1/2-approximable.

Recommendations

• scientific article; zbMATH DE number 4132836
• Approximation in multiobjective optimization
• Approximation methods in multiobjective programming
• scientific article; zbMATH DE number 1830716
• On approximate solutions in multiobjective optimization
• Approximate solutions of multiobjective optimization problems
• Approximation methods for multiobjective and parametric optimization problems
• Approximation Methods for Multiobjective Optimization Problems: A Survey
• Optimality conditions for approximate solutions in multiobjective optimization problems
• On the quality of discrete representations in multiple objective programming

Cited in

(5)

• Multi-criteria TSP: Min and Max combined
• Approximation Methods for Multiobjective Optimization Problems: A Survey
• scientific article; zbMATH DE number 5630417 (Why is no real title available?)
• Simultaneous approximation of constraint satisfaction problems
• Deterministic algorithms for multi-criteria max-TSP

This page was built for publication: Applications of discrepancy theory in multiobjective approximation

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