Search

Your search keyword '"Kerivin, Hervé"' showing total 40 results
Start Over Author "Kerivin, Hervé"
40 results on '"Kerivin, Hervé"'

1. Comparative study of quantum methods in the resolution of track findings instances

Author

Do, Duy Dao, Kerivin, Hervé, Lacomme, Philippe, and Vulpescu, Bogdan

Subjects
Quantum Physics
Abstract

Track finding can be considered as a complex optimization problem initially introduced in particle physics involving the reconstruction of particle trajectories. A track is typically composed of several consecutive segments (track segments) that resembles a smooth curve without bifurcations. In this paper various modeling approaches are explored in order to assess both their impact and their effectiveness in solving them using quantum and classical methods. We present implementations of three classical models using CPLEX, two quantum models running on actual D-Wave quantum computers, and one quantum model on a D-Wave simulator. To facilitate a fair comparative study and encourage future research in this area, we introduce a new set of benchmark instances, categorized into small, medium, and large scales. Our evaluation of these methods on the benchmark instances indicates that D-Wave methods offer an excellent balance between computation time and result quality, outperforming CPLEX in numerous cases.

Published
2024

5. On Superperfection of Edge Intersection Graphs of Paths

Author

Kerivin, Hervé, Wagler, Annegret, Vigo, Daniele, Editor-in-Chief, Agnetis, Alessandro, Series Editor, Amaldi, Edoardo, Series Editor, Guerriero, Francesca, Series Editor, Lucidi, Stefano, Series Editor, Messina, Enza, Series Editor, Sforza, Antonio, Series Editor, Gentile, Claudio, editor, Stecca, Giuseppe, editor, and Ventura, Paolo, editor

Published
2021
Full Text
View/download PDF

7. The Stop Number Minimization Problem: Complexity and Polyhedral Analysis

Author

Baïou, Mourad, Colares, Rafael, Kerivin, Hervé, Hutchison, David, Series Editor, Kanade, Takeo, Series Editor, Kittler, Josef, Series Editor, Kleinberg, Jon M., Series Editor, Mattern, Friedemann, Series Editor, Mitchell, John C., Series Editor, Naor, Moni, Series Editor, Pandu Rangan, C., Series Editor, Steffen, Bernhard, Series Editor, Terzopoulos, Demetri, Series Editor, Tygar, Doug, Series Editor, Weikum, Gerhard, Series Editor, Lee, Jon, editor, Rinaldi, Giovanni, editor, and Mahjoub, A. Ridha, editor

Published
2018
Full Text
View/download PDF

8. Maximum Bounded Rooted-Tree Packing Problem

Author

Kerivin, Herve, Leblet, Jimmy, Simon, Gwendal, and Zhou, Fen

Subjects
Computer Science - Computational Complexity
Abstract

Given a graph and a root, the Maximum Bounded Rooted-Tree Packing (MBRTP) problem aims at finding K rooted-trees that span the largest subset of vertices, when each vertex has a limited outdegree. This problem is motivated by peer-to-peer streaming overlays in under-provisioned systems. We prove that the MBRTP problem is NP-complete. We present two polynomial-time algorithms that computes an optimal solution on complete graphs and trees respectively.

Published
2011

9. A note on the data-driven capacity of P2P networks

Author

Chakareski, Jacob, Frossard, Pascal, Kerivin, Hervé, Leblet, Jimmy, and Simon, Gwendal

Subjects
Computer Science - Data Structures and Algorithms, Computer Science - Networking and Internet Architecture
Abstract

We consider two capacity problems in P2P networks. In the first one, the nodes have an infinite amount of data to send and the goal is to optimally allocate their uplink bandwidths such that the demands of every peer in terms of receiving data rate are met. We solve this problem through a mapping from a node-weighted graph featuring two labels per node to a max flow problem on an edge-weighted bipartite graph. In the second problem under consideration, the resource allocation is driven by the availability of the data resource that the peers are interested in sharing. That is a node cannot allocate its uplink resources unless it has data to transmit first. The problem of uplink bandwidth allocation is then equivalent to constructing a set of directed trees in the overlay such that the number of nodes receiving the data is maximized while the uplink capacities of the peers are not exceeded. We show that the problem is NP-complete, and provide a linear programming decomposition decoupling it into a master problem and multiple slave subproblems that can be resolved in polynomial time. We also design a heuristic algorithm in order to compute a suboptimal solution in a reasonable time. This algorithm requires only a local knowledge from nodes, so it should support distributed implementations. We analyze both problems through a series of simulation experiments featuring different network sizes and network densities. On large networks, we compare our heuristic and its variants with a genetic algorithm and show that our heuristic computes the better resource allocation. On smaller networks, we contrast these performances to that of the exact algorithm and show that resource allocation fulfilling a large part of the peer can be found, even for hard configuration where no resources are in excess., Comment: 10 pages, technical report assisting a submission

Published
2009

10. Solving the routing and spectrum assignment problem, driven by combinatorial properties.

Author

da Silva, Pedro Henrique Fernandes, Kerivin, Hervé, Nant, Juan Pablo, and Wagler, Annegret K.

Subjects
LINEAR programming, NP-hard problems, ROUTING algorithms, INTEGER programming, ASSIGNMENT problems (Programming)
Abstract

The routing and spectrum assignment problem in modern optical networks is an NP‐hard problem that has received increasing attention during the last years. The majority of existing integer linear programming models for the problem uses edge‐path formulations where variables are associated with all possible routing paths so that the number of variables grows exponentially with the size of the instance. To bypass this difficulty, precomputed subsets of all possible paths per demand are typically used, which cannot guarantee optimality of the solutions in general. Our contribution is to provide a framework for the use of edge‐path formulations to minimize the spectrum width of a solution. For that, we select an appropriate subset of paths to operate on with the help of combinatorial properties in such a way that optimality of the solution can be guaranteed. Computational results indicate that our approach is indeed promising to solve the routing and spectrum assignment problem. [ABSTRACT FROM AUTHOR]

Published
2024
Full Text
View/download PDF

15. Connected subgraphs, matching, and partitions

Author

Biha, Mohamed, Kerivin, Hervé, Laboratoire de Mathématiques Nicolas Oresme (LMNO), Université de Caen Normandie (UNICAEN), Normandie Université (NU)-Normandie Université (NU)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne (UCA)-Institut national polytechnique Clermont Auvergne (INP Clermont Auvergne), and Université Clermont Auvergne (UCA)-Université Clermont Auvergne (UCA)

Subjects
separation, matching, polytope, [INFO]Computer Science [cs], [MATH]Mathematics [math], partition, connected subgraph
Abstract

Given an undirected graph G and a real edge-weight vector, the connected subgraph problem consists of finding a maximum-weight subset of edges which induces a connected subgraph of G. In this paper, we establish a link between the complexity of the connected subgraph problem and the matching number. We study the separation problem associated with the Matching-partition inequalities wich are introduced by Didi Biha et al. [4] for the connected subgraph polytope.

Published
2023

17. Impact of RSA Optimization Objectives on Optical Network State

Author

Chouman, Hussein, Gravey, Annie, Gravey, Philippe, Hadhbi, Youssouf, Kerivin, Hervé, Morvan, Michel, Wagler, Annegret, IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT), Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne (UCA)-Institut national polytechnique Clermont Auvergne (INP Clermont Auvergne), Université Clermont Auvergne (UCA)-Université Clermont Auvergne (UCA), Wagler, Annegret, IMT Atlantique (IMT Atlantique), and Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne (UCA)-Institut national polytechnique Clermont Auvergne (INP Clermont Auvergne)

Subjects
[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], RSA, [INFO.INFO-CE]Computer Science [cs]/Computational Engineering, Finance, and Science [cs.CE], flexgrid, [INFO.INFO-CE] Computer Science [cs]/Computational Engineering, Finance, and Science [cs.CE], Optical network, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], optimization
Abstract

This paper focuses on off-line dimensioning offlexgrid networks. As any operator wishes to satisfy all trafficdemands characterized by a traffic matrix, considering blockingas an optimization objective is not appropriate. We thus considertwo other objectives, one of them related to path lengths and theother related to spectrum occupancy. We also define several indi-cators to characterize a mapping of demands on a given network,including some which are related to the remaining capacity ofthe network. We apply off-line dimensioning algorithms with thetwo different optimization objectives on a traffic matrix to besupported by a small flexgrid network and assess the impact ofthe selected optimization objective on the network level metricsin order to provide insight on how such an off-line dimensioningshould be performed.

Published
2021

18. An extended formulation for the Constraint Routing and Spectrum Assignment Problem in Elastic Optical Networks *

Author

Colares, Rafael, Kerivin, Hervé, Wagler, Annegret, Wagler, Annegret, Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne (UCA)-Institut national polytechnique Clermont Auvergne (INP Clermont Auvergne), Université Clermont Auvergne (UCA)-Université Clermont Auvergne (UCA), and Ecole Nationale Supérieure des Mines de St Etienne-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne (UCA)-Institut national polytechnique Clermont Auvergne (INP Clermont Auvergne)

Subjects
[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], ComputerSystemsOrganization_COMPUTER-COMMUNICATIONNETWORKS, Computer Science::Networking and Internet Architecture, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Abstract

The emergence of Elastic Optical Networks allowed a more flexible spectrum allocation for routing traffic demands within telecommunication networks. From this context arises the Routing and Spectrum Assignment problem, which consists of routing a given set of origin-destination traffic demands and assigning them to contiguous spectrum frequencies such that no frequency slot is assigned to more than one demand within a network link. This work deals with the variant where each demand route must additionally satisfy a maximal-length constraint. In this paper we propose a compact extended formulation for the Constrained Routing and Spectrum Assignment Problem. We show that our extended formulation is theoretically stronger than formulations known in the literature. Experimental results demonstrate the efficiency of our approach.

Published
2021

19. Assessing the Health of Flexgrid Optical Networks

Author

Chouman, Hussein, Luay, Alahdab, Colares, Rafael, Gravey, Annie, Gravey, Philippe, Kerivin, Hervé, Morvan, Michel, Wagler, Annegret, Département Optique (IMT Atlantique - OPT), IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne [2017-2020] (UCA [2017-2020]), CNET, Centre National d'Etudes des Télécommunications, Laboratoire d'Informatique, de Modélisation et d'optimisation des Systèmes (LIMOS), SIGMA Clermont (SIGMA Clermont)-Université d'Auvergne - Clermont-Ferrand I (UdA)-Ecole Nationale Supérieure des Mines de St Etienne-Centre National de la Recherche Scientifique (CNRS)-Université Blaise Pascal - Clermont-Ferrand 2 (UBP), LIMOS (UMR CNRS 6158), université Clermont Auvergne, France, Institut Mines Telecom, IMT Atlantique, Brest, IMT Atlantique (IMT Atlantique), Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Université Clermont Auvergne [2017-2020] (UCA [2017-2020])-Centre National de la Recherche Scientifique (CNRS), and Université Blaise Pascal - Clermont-Ferrand 2 (UBP)-Université d'Auvergne - Clermont-Ferrand I (UdA)-SIGMA Clermont (SIGMA Clermont)-Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Centre National de la Recherche Scientifique (CNRS)

Subjects
[INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI]
Published
2020

29. NEW ECONOMICAL VIRTUAL PRIVATE NETWORKS.

Author

Ben-Ameur, Walid and Kerivin, Hervé

Subjects
*VIRTUAL private networks, *TELECOMMUNICATION, *PRIVATE networks, *COMPUTER networks, *COMPUTER network resources, *INFORMATION resources management, *BUSINESS communication
Abstract

This article focuses on new economical virtual private networks (VPN). Telecommunication operators can use newly developed telecommunication design methodology to account for the uncertainty of traffic among corporate sites and develop economical virtual private networks for their prospective corporate customers. A VPN is a general purpose communication environment allowing user organizations to communicate privately, securely and transparently through shared resources provided by telecommunication operators. They are one of the most profitable services for long-distance carriers. An economical VPN architecture can be configured and provided by many telecommunication operators. One of the most important issues to be studied by them is the pricing of the service. Three important properties introduced help operators propose pricing models: profit, simplicity and coherence. The new economical VPN now herald the field's next generation. The cost of an economical VPN can be much lower than the cost of a classical VPN and traffic variations can be more easily taken into account.

Published
2003
Full Text
View/download PDF

30. Heuristic for the preemptive asymmetric stacker crane problem

Author

Kerivin, Hervé, Lacroix, Mathieu, Quilliot, Alain, Toussaint, Hélène, Laboratoire d'Informatique, de Modélisation et d'optimisation des Systèmes (LIMOS), SIGMA Clermont (SIGMA Clermont)-Université d'Auvergne - Clermont-Ferrand I (UdA)-Ecole Nationale Supérieure des Mines de St Etienne-Centre National de la Recherche Scientifique (CNRS)-Université Blaise Pascal - Clermont-Ferrand 2 (UBP), and Université Blaise Pascal - Clermont-Ferrand 2 (UBP)-Université d'Auvergne - Clermont-Ferrand I (UdA)-SIGMA Clermont (SIGMA Clermont)-Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Centre National de la Recherche Scientifique (CNRS)

Subjects
preemptive asymmetric stacker crane problem, routing, local search, reloads, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], heuristic design
Abstract

International audience; In this paper, we deal with the preemptive asymmetric stacker crane problem in an heuristic way. We first present some theoretical results which allow us to turn this problem into a specific tree design problem. We next derive from this new representation a simple, efficient local search heuristic, as well as an original LIP model. We conclude by presenting experimental results which aim at both testing the efficiency of our heuristic and at evaluating the impact of the preemption hypothesis.

Published
2010

38. ON THE POLYTOPE OF THE (1,2)-SURVIVABLE NETWORK DESIGN PROBLEM.

Author

Didi Biha, Mohamed, Kerivin, Hervé, and Mahjoub, Ridha

Subjects
*POLYTOPES, *HYPERSPACE, *TOPOLOGY, *GRAPH theory, *POLYNOMIALS
Abstract

This paper deals with the survivable network design problem where each node v has a connectivity type r(v) equal to 1 or 2, and the survivability conditions require the existence of at least min{r(s), r(t)} edge-disjoint paths for all distinct nodes s and t. We consider the polytope given by the trivial and cut inequalities together with the partition inequalities. More precisely, we study some structural properties of this polytope which leads us to give some sufficient conditions for this polytope to be integer in the class of series-parallel graphs. With both separation problems for the cut and partition inequalities being polynomially solvable, we then obtain a polynomial time algorithm for the (1,2)-survivable network design problem in a subclass of series-parallel graphs including the outerplanar graph class. We also introduce a new class of facet-defining inequalities for the polytope associated to the (1,2)-survivable network design problem. [ABSTRACT FROM AUTHOR]

Published
2008
Full Text
View/download PDF

39. Design of Capacitated Survivable Networks With a Single Facility.

Author

Kerivin, Hervé, Nace, Dritan, and Pham, Thi-Tuyet-Loan

Subjects
COMPUTER networks, ELECTRIC network topology, TELECOMMUNICATION traffic, LINEAR programming, INTEGER programming, MATHEMATICAL decomposition
Abstract

In this paper we focus on the single-facility capacitated survivable network design problem. We optimize simultaneously the network topology and the link dimensioning in order to route all traffic commodities according to survivability requirements. The latter are actually expressed in terms of the spare capacity required to address link failures in the context of different rerouting strategies. We present a mixed-integer linear programming model solved by combining several approaches. To tackle the high dimensionality and to separate the continuous and integer variables, we use Benders' decomposition and a cutting-plane approach. Going beyond the proposed method itself, we examine and compare two well-known restoration techniques: local and end-to-end reroutings. Numerous computational results for realistic network instances provide a comparison of these rerouting mechanisms in terms of installed capacities, network density as well as overall costs and CPU time. [ABSTRACT FROM AUTHOR]

Published
2005
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results