A new modeling and solution approach for the number partitioning problem.
A note on minimum rank and maximum nullity of sign patterns.
A note on the hardness results for the labeled perfect matching problems in bipartite graphs
In this note, we strengthen the inapproximation bound of O(logn) for the labeled perfect matching problem established in J. Monnot, The Labeled perfect matching in bipartite graphs, Information Processing Letters96 (2005) 81–88, using a self improving operation in some hard instances. It is interesting to note that this self improving operation does not work for all instances. Moreover, based on this approach we deduce that the problem does not admit constant approximation algorithms for connected...
A space lower bound for acceptance by one-way -alternating machines
A Space Lower Bound for Acceptance by One-Way Π2-Alternating Machines
We show that one-way Π2-alternating Turing machines cannot accept unary nonregular languages in o(log n) space. This holds for an accept mode of space complexity measure, defined as the worst cost of any accepting computation. This lower bound should be compared with the corresponding bound for one-way Σ2-alternating machines, that are able to accept unary nonregular languages in space O(log log n). Thus, Σ2-alternation is more powerful than Π2-alternation for space bounded one-way machines with...
A survey on combinatorial optimization in dynamic environments∗
This survey presents major results and issues related to the study of NPO problems in dynamic environments, that is, in settings where instances are allowed to undergo some modifications over time. In particular, the survey focuses on two complementary frameworks. The first one is the reoptimization framework, where an instance I that is already solved undergoes some local perturbation. The goal is then to make use of the information provided by the initial solution to compute a new solution. The...
A survey on combinatorial optimization in dynamic environments∗
This survey presents major results and issues related to the study of NPO problems in dynamic environments, that is, in settings where instances are allowed to undergo some modifications over time. In particular, the survey focuses on two complementary frameworks. The first one is the reoptimization framework, where an instance I that is already solved undergoes some local perturbation. The goal is then to make use of the information provided by the initial solution to compute a new solution. The...
An Oriented Version of the 1-2-3 Conjecture
The well-known 1-2-3 Conjecture addressed by Karoński, Luczak and Thomason asks whether the edges of every undirected graph G with no isolated edge can be assigned weights from {1, 2, 3} so that the sum of incident weights at each vertex yields a proper vertex-colouring of G. In this work, we consider a similar problem for oriented graphs. We show that the arcs of every oriented graph −G⃗ can be assigned weights from {1, 2, 3} so that every two adjacent vertices of −G⃗ receive distinct sums of outgoing...
Automated proofs of upper bounds on the running time of splitting algorithms.
Autour de nouvelles notions pour l’analyse des algorithmes d’approximation : formalisme unifié et classes d’approximation
The main objective of the polynomial approximation is the development of polynomial time algorithms for NP-hard problems, these algorithms guaranteeing feasible solutions lying “as near as possible” to the optimal ones. This work is the fist part of a couple of papers where we introduce the key-concepts of the polynomial approximation and present the main lines of a new formalism. Our purposes are, on the one hand, to present this theory and its objectives and, on the other hand, to discuss the...
Autour de nouvelles notions pour l’analyse des algorithmes d’approximation : de la structure de NPO à la structure des instances
Cet article est la suite de l’article «Autour de nouvelles notions pour l’analyse des algorithmes d’approximation : formalisme unifié et classes d’approximation» où nous avons présenté et discuté, dans le cadre d’un nouveau formalisme pour l’approximation polynomiale (algorithmique polynomiale à garanties de performances pour des problèmes NP-difficiles), des outils permettant d’évaluer, dans l’absolu, les proporiétés d’approximation de problèmes difficiles. Afin de répondre pleinement à l’objectif...
Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances
This paper is the continuation of the paper “Autour de nouvelles notions pour l'analyse des algorithmes d'approximation: Formalisme unifié et classes d'approximation” where a new formalism for polynomial approximation and its basic tools allowing an “absolute” (individual) evaluation the approximability properties of NP-hard problems have been presented and discussed. In order to be used for exhibiting a structure for the class NPO (the optimization problems of NP), these tools must be enriched...
Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : formalisme unifié et classes d'approximation
Cet article est le premier d'une série de deux articles où nous présentons les principales caractéristiques d'un nouveau formalisme pour l'approximation polynomiale (algorithmique polynomiale à garanties de performances pour les problèmes NP-difficiles). Ce travail est l'occasion d'un regard critique sur ce domaine et de discussions sur la pertinence des notions usuelles. Il est aussi l'occasion de se familiariser avec l'approximation polynomiale, de comprendre ses enjeux et ses méthodes. Ces deux...