On Geometric Optimization with Few Violated Constraints.
On the complexities of selected satisfiability and equivalence queries over Boolean formulas and inclusion queries over hulls.
On the complexity of determining tolerances for ε-optimal solutions to min-max combinatorial optimization problems
This paper studies the complexity of sensitivity analysis for optimal and ε-optimal solutions to general 0-1 combinatorial optimization problems with min-max objectives. Van Hoesel and Wagelmans [9] have studied the complexity of sensitivity analysis of optimal and ε-optimal solutions to min-sum problems, and Ramaswamy et al. [17] the complexity of sensitivity analysis of optimal solutions to min-max problems. We show that under some mild assumptions the sensitivity analysis of ε-optimal solutions...
On the complexity of -player Hackenbush.
Open shop scheduling with delays
Optimal scheduling of the -machine assembly-type flow shop
Optimal scheduling of the 3-machine assembly-type flow shop
We address the 3-Machine Assembly-Type Flowshop Scheduling Problem (3MAF). This problem is known to be NP-complete in the strong sense. We propose an exact branch and bound method based on a recursive enumeration of potential inputs and outputs of the machines. Using this algorithm, several large size instances have been solved to optimality.
Optimal tool partitioning rules for numerically controlled punch press operations
Ordres médians et ordres de Slater des tournois
Dans cet article, nous essayons de faire le point sur les résultats concernant les aspects combinatoires et algorithmiques des ordres médians et des ordres de Slater des tournois. La plupart des résultats recensés sont tirés de différentes publications ; plusieurs sont originaux.