Show simple item record

hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorBazgan, Cristina
hal.structure.identifierDepartment of Mathematics, University of Kaiserslautern
dc.contributor.authorHerzel, Arne
hal.structure.identifierDepartment of Mathematics, University of Kaiserslautern
dc.contributor.authorRuzika, Stefan
hal.structure.identifierDepartment of Mathematics, University of Kaiserslautern
dc.contributor.authorThielen, Clemens
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorVanderpooten, Daniel
dc.date.accessioned2019-10-09T10:46:27Z
dc.date.available2019-10-09T10:46:27Z
dc.date.issued2019
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/20058
dc.descriptionLecture Notes in Computer Science book series (LNCS, volume 11653)en
dc.language.isoenen
dc.subjectParametric optimizationen
dc.subjectApproximation schemeen
dc.subjectParametric assignment problemen
dc.subjectParametric minimum-cost flow problemen
dc.subjectParametric shortest path problemen
dc.subject.ddc003en
dc.titleAn FPTAS for a General Class of Parametric Optimization Problemsen
dc.typeCommunication / Conférence
dc.description.abstractenIn a (linear) parametric optimization problem, the objective value of each feasible solution is an affine function of a real-valued parameter and one is interested in computing a solution for each possible value of the parameter. For many important parametric optimization problems including the parametric versions of the shortest path problem, the assignment problem, and the minimum cost flow problem, however, the piecewise linear function mapping the parameter to the optimal objective value of the corresponding non-parametric instance (the optimal value function) can have super-polynomially many breakpoints (points of slope change). This implies that any optimal algorithm for such a problem must output a super-polynomial number of solutions.We provide a (parametric) fully-polynomial time approximation scheme for a general class of parametric optimization problems for which (i) the parameter varies on the nonnegative real line, (ii) the non-parametric problem is solvable in polynomial time, and (iii) the slopes and intercepts of the value functions of the feasible solutions are nonnegative, integer values below a polynomial-time computable upper bound. In particular, under mild assumptions, we obtain the first parametric FPTAS for each of the specific problems mentioned above.en
dc.identifier.citationpages25-37en
dc.relation.ispartoftitleComputing and Combinatorics 25th International Conference, COCOON 2019, Proceedingsen
dc.relation.ispartofeditorDu, Ding-Zhu
dc.relation.ispartofeditorDuan, Zhenhua
dc.relation.ispartofeditorTian, Cong
dc.relation.ispartofpublnameSpringeren
dc.relation.ispartofdate2019
dc.relation.ispartofpages678en
dc.relation.ispartofurl10.1007/978-3-030-26176-4en
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.ispartofisbn978-3-030-26175-7en
dc.relation.conftitle25th International Conference, COCOON 2019en
dc.relation.confdate2019-07
dc.relation.confcityXi'anen
dc.relation.confcountryChinaen
dc.relation.forthcomingnonen
dc.identifier.doi10.1007/978-3-030-26176-4_3en
dc.description.ssrncandidatenonen
dc.description.halcandidateouien
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewednonen
dc.relation.Isversionofjnlpeerreviewednonen
dc.date.updated2019-10-09T10:38:57Z
hal.identifierhal-02309541*
hal.version1*
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record