Scheduling trajectories on a planar surface with moving obstacles.
Semi-definite positive programming relaxations for graph K-coloring in frequency assignment
In this paper we will describe a new class of coloring problems, arising from military frequency assignment, where we want to minimize the number of distinct -uples of colors used to color a given set of -complete-subgraphs of a graph. We will propose two relaxations based on Semi-Definite Programming models for graph and hypergraph coloring, to approximate those (generally) NP-hard problems, as well as a generalization of the works of Karger et al. for hypergraph coloring, to find good feasible...
Semi-Definite positive Programming Relaxations for Graph Kn-Coloring in Frequency Assignment
In this paper we will describe a new class of coloring problems, arising from military frequency assignment, where we want to minimize the number of distinct n-uples of colors used to color a given set of n-complete-subgraphs of a graph. We will propose two relaxations based on Semi-Definite Programming models for graph and hypergraph coloring, to approximate those (generally) NP-hard problems, as well as a generalization of the works of Karger et al. for hypergraph coloring, to find good feasible...
Semidefinite Programming Based Algorithms for the Sparsest Cut Problem
In this paper we analyze a known relaxation for the Sparsest Cut problem based on positive semidefinite constraints, and we present a branch and bound algorithm and heuristics based on this relaxation. The relaxed formulation and the algorithms were tested on small and moderate sized instances. It leads to values very close to the optimum solution values. The exact algorithm could obtain solutions for small and moderate sized instances, and the best heuristics obtained optimum or near optimum...
Semidefinite Programming Based Algorithms for the Sparsest Cut Problem
In this paper we analyze a known relaxation for the Sparsest Cut problem based on positive semidefinite constraints, and we present a branch and bound algorithm and heuristics based on this relaxation. The relaxed formulation and the algorithms were tested on small and moderate sized instances. It leads to values very close to the optimum solution values. The exact algorithm could obtain solutions for small and moderate sized instances, and the best heuristics obtained optimum or near optimum...
Sensitivity Analysis of Network Optimization Problems
Sensor Location Problem for a Multigraph
MSC 2010: 05C50, 15A03, 15A06, 65K05, 90C08, 90C35We introduce sparse linear underdetermined systems with embedded network structure. Their structure is inherited from the non-homogeneous network ow programming problems with nodes of variable intensities. One of the new applications of the researched underdetermined systems is the sensor location problem (SLP) for a multigraph. That is the location of the minimum number of sensors in the nodes of the multigraph, in order to determine the arcs ow...
Single-commodity vehicle routing problem with pickup and delivery service.
Some remarks on two degrees of asymmetry in the traveling salesman problem
Stochastic bottleneck transportation problem with flexible supply and demand quantity
We consider the following bottleneck transportation problem with both random and fuzzy factors. There exist supply points with flexible supply quantity and demand points with flexible demand quantity. For each supply-demand point pair, the transportation time is an independent positive random variable according to a normal distribution. Satisfaction degrees about the supply and demand quantity are attached to each supply and each demand point, respectively. They are denoted by membership functions...
Structures algébriques généralisées des problèmes de cheminement dans les graphes
Sum-Of-Squares Clustering on Networks
Sur le problème du couplage maximal
Sur les performances d'algorithmes de recherche de chemins minimaux dans les graphes clairsemés
Sur quelques formes quadratiques associées à des partitions d'entiers