All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 2 Next

Displaying 21 – 40 of 55

Showing per page

Complexity of partial inverse assignment problem and partial inverse cut problem

Xiaoguang Yang (2001)

RAIRO - Operations Research - Recherche Opérationnelle

For a given partial solution, the partial inverse problem is to modify the coefficients such that there is a full solution containing the partial solution, while the full solution becomes optimal under new coefficients, and the total modification is minimum. In this paper, we show that the partial inverse assignment problem and the partial inverse minimum cut problem are NP-hard if there are bound constraints on the changes of coefficients.

Complexity of Partial Inverse Assignment Problem and Partial Inverse Cut Problem

Xiaoguang Yang (2010)

RAIRO - Operations Research

For a given partial solution, the partial inverse problem is to modify the coefficients such that there is a full solution containing the partial solution, while the full solution becomes optimal under new coefficients, and the total modification is minimum. In this paper, we show that the partial inverse assignment problem and the partial inverse minimum cut problem are NP-hard if there are bound constraints on the changes of coefficients.

Differential approximation of NP-hard problems with equal size feasible solutions

Jérôme Monnot (2002)

RAIRO - Operations Research - Recherche Opérationnelle

In this paper, we focus on some specific optimization problems from graph theory, those for which all feasible solutions have an equal size that depends on the instance size. Once having provided a formal definition of this class of problems, we try to extract some of its basic properties; most of these are deduced from the equivalence, under differential approximation, between two versions of a problem π which only differ on a linear transformation of their objective functions. This is notably...

Differential approximation of NP-hard problems with equal size feasible solutions

Jérôme Monnot (2010)

RAIRO - Operations Research

In this paper, we focus on some specific optimization problems from graph theory, those for which all feasible solutions have an equal size that depends on the instance size. Once having provided a formal definition of this class of problems, we try to extract some of its basic properties; most of these are deduced from the equivalence, under differential approximation, between two versions of a problem π which only differ on a linear transformation of their objective functions. This is notably...

Hybrid flow-shop with adjustment

Jan Pelikán (2011)

Kybernetika

The subject of this paper is a flow-shop based on a case study aimed at the optimisation of ordering production jobs in mechanical engineering, in order to minimize the overall processing time, the makespan. The production jobs are processed by machines, and each job is assigned to a certain machine for technological reasons. Before processing a job, the machine has to be adjusted; there is only one adjuster who adjusts all of the machines. This problem is treated as a hybrid two-stage flow-shop:...

Internet shopping optimization problem

Jacek Błażewicz, Mikhail Y. Kovalyov, Jędrzej Musiał, Andrzej P. Urbański, Adam Wojciechowski (2010)

International Journal of Applied Mathematics and Computer Science

A high number of Internet shops makes it difficult for a customer to review manually all the available offers and select optimal outlets for shopping. A partial solution to the problem is brought by price comparators which produce price rankings from collected offers. However, their possibilities are limited to a comparison of offers for a single product requested by the customer. The issue we investigate in this paper is a multiple-item multiple-shop optimization problem, in which total expenses...

New algorithms for coupled tasks scheduling – a survey

Jacek Blazewicz, Grzegorz Pawlak, Michal Tanas, Wojciech Wojciechowicz (2012)

RAIRO - Operations Research - Recherche Opérationnelle

The coupled tasks scheduling problem is a class of scheduling problems introduced for beam steering software of sophisticated radar devices, called phased arrays. Due to increasing popularity of such radars, the importance of coupled tasks scheduling is constantly growing. Unfortunately, most of the coupled tasks problems are NP-hard, and only a few practically usable algorithms for such problems were found. This paper provides a survey of already known complexity results of various variants of...

On the complexity of determining tolerances for ε-optimal solutions to min-max combinatorial optimization problems

Diptesh Ghosh, Gerard Sierksma (2003)

Applicationes Mathematicae

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...

Currently displaying 21 – 40 of 55