How good is the Chord algorithm?

DOI10.1137/13093875XMaRDI QIDQ2816293zbMATH OpenFDO

Authors Constantinos Daskalakis, Ilias Diakonikolas, Mihalis Yannakakis

Publication date 4 July 2016

Published in SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

approximationmultiobjective optimizationchord algorithmconvex Pareto set

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Recommendations

• How good is the chord algorithm?
• How good are convex hull algorithms?
• scientific article; zbMATH DE number 653261
• Is the Euclidean Algorithm Optimal Among its Peers?
• How fast can the chord length distribution decay?
• scientific article; zbMATH DE number 579377
• A parameterized algorithm for chordal sandwich
• scientific article; zbMATH DE number 1256761

Cites work

• scientific article; zbMATH DE number 5764846 (Why is no real title available?)
• A method for convex curve approximation
• A survey and annotated bibliography of multiobjective combinatorial optimization
• Approximation methods in multiobjective programming
• Approximation of convex curves with application to the bicriterial minimum cost flow problem
• Bicriteria Transportation Problem
• Efficiently computing succinct trade-off curves
• Mathematical Techniques for Efficient Record Segmentation in Large Shared Databases
• Multicriteria Optimization
• Multiple criteria decision analysis. State of the art surveys
• Nonlinear multiobjective optimization
• Sandwich approximation of univariate convex functions with an application to separable convex programming
• Shape from probing
• Small approximate Pareto sets for biobjective shortest paths and other problems
• The convergence rate of the sandwich algorithm for approximating convex functions
• \(\epsilon\)-optimality for bicriteria programs and its application to minimum cost flows

Cited in

(7)

• The power of the weighted sum scalarization for approximating multiobjective optimization problems
• Approximation Methods for Multiobjective Optimization Problems: A Survey
• Using scalarizations for the approximation of multiobjective optimization problems: towards a general theory
• An approximation algorithm for a general class of parametric optimization problems
• How good is the chord algorithm?
• An approximation algorithm for a general class of multi-parametric optimization problems
• Approximating biobjective minimization problems using general ordering cones

This page was built for publication: How good is the Chord algorithm?

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