An approximation algorithm for a general class of multi-parametric optimization problems
DOI10.1007/s10878-022-00902-wzbMath1501.90097arXiv2109.10076OpenAlexW3199011140WikidataQ114225843 ScholiaQ114225843MaRDI QIDQ2082173
Stephan Helfrich, Stefan Ruzika, Clemens Thielen, Arne Herzel
Publication date: 4 October 2022
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2109.10076
approximation algorithmmulti-parametric knapsack problemmulti-parametric maximization of independence systemsmulti-parametric minimum \(s\)-\(t\)-cut problemmulti-parametric optimization
Sensitivity, stability, parametric optimization (90C31) Combinatorial optimization (90C27) Approximation algorithms (68W25)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Theoretical and algorithmic advances in multi-parametric programming and control
- Approximation schemes for the parametric knapsack problem
- Strongly polynomial bounds for multiobjective and parametric global minimum cuts in graphs and hypergraphs
- Parametric shortest path algorithms with an application to cyclic staffing
- A new fully polynomial time approximation scheme for the Knapsack problem
- Geometric algorithms and combinatorial optimization.
- Improved dynamic programming in connection with an FPTAS for the knapsack problem
- An approximation algorithm for a general class of parametric optimization problems
- An FPTAS for the knapsack problem with parametric weights
- An FPTAS for the parametric knapsack problem
- Efficiently computing succinct trade-off curves
- Complexity of source-sink monotone 2-parameter min cut
- How Good is the Chord Algorithm?
- The Design of Approximation Algorithms
- A fast parametric assignment algorithm with applications in max-algebra
- Max-Balancing Weighted Directed Graphs and Matrix Scaling
- Computing optimal scalings by parametric network algorithms
- A minimum concave-cost dynamic network flow problem with an application to lot-sizing
- Complexity of some parametric integer and network programming problems
- Complexity results for multicriterial and parametric network flows using a pathological graph of Zadeh
- Mathematical Techniques for Efficient Record Segmentation in Large Shared Databases
- An Analysis of the Greedy Heuristic for Independence Systems
- Parametric Solution for Linear Bicriteria Knapsack Models
- A Fast Parametric Maximum Flow Algorithm and Applications
- Fast Algorithms for Parametric Scheduling Come From Extensions to Parametric Maximum Flow
- Approximation Methods for Multiobjective Optimization Problems: A Survey
- Enumerating parametric global minimum cuts by random interleaving
- Parametric Objective Function (Part 1)
- Parametric Objective Function (Part 2)—Generalization
- Greedy in Approximation Algorithms
- Stochastic Shortest Paths Via Quasi-convex Maximization
- Max flows in O(nm) time, or better
- Multiparametric Linear Programming
- Faster parametric shortest path and minimum‐balance algorithms
- A lower bound for the shortest path problem
This page was built for publication: An approximation algorithm for a general class of multi-parametric optimization problems
