Volume 6, numéro 2, fall 2011

EN :

We consider scheduling weighted packets with time constraints over a fading channel. Packets arrive at the transmitter in an online manner. Each packet has a value and a deadline by which it should be sent. The fade state of the channel determines the throughput obtained per time unit and the channel’s quality may change over time. In this paper, we design both offline and online algorithms to maximize weighted throughput, defined as the total value of the packets sent by their respective deadlines. We first present polynomial-time exact offline algorithms for this problem. We then present online algorithms and their competitive analysis. We also show the lower bounds of competitive ratio.

EN :

We show here that the implementation of the Markov random fields image segmentation algorithm of Hochbaum 2001 works well for the purpose of denoising and segmenting medical images. One of the main contributions here is the ability for a user to manipulate online the image so as to achieve clear delineation of objects of interest in the image. This is made possible by the efficiency of the implementation. Results are presented for images that are generated by Single Photon Emission Computed Tomography and Magnetic Resonance Imaging. The results show that the method presented is effective at denoising medical images as well as segmenting tissue types, organs, lesions, and other features within medical images. We advocate that this method should be considered as part of the medical imaging toolbox.

EN :

The shortest path problem in which the (s, t)-paths P of a given digraph G = (V, E) are compared with respect to the sum of their edge costs is one of the best known problems in combinatorial optimization. The paper is concerned with a number of variations of this problem having different objective functions like bottleneck, balanced, minimum deviation, algebraic sum, k-sum and k-max objectives, (k₁, k₂)-max, (k₁, k₂)-balanced and several types of trimmed-mean objectives. We give a survey on existing algorithms and propose a general model for those problems not yet treated in literature. The latter is based on the solution of resource constrained shortest path problems with equality constraints which can be solved in pseudo-polynomial time if the given graph is acyclic and the number of resources is fixed. In our setting, however, these problems can be solved in strongly polynomial time. Combining this with known results on k-sum and k-max optimization for general combinatorial problems, we obtain strongly polynomial algorithms for a variety of path problems on acyclic and general digraphs.

EN :

The paper considers the problem of maximizing the profits of a retailer operating in the Italian electricity market. The problem consists in selecting the contracts portfolio and in defining the bidding strategy in the wholesales market while respecting the technical and regulatory constraints. A novel solution method based on a enhanced discovery of the search domain in the simulated annealing technique has been developed for its solution and a set of realistic test problems have been generated for its validation. The experimental results show that our method outperforms the standard simulated annealing by an improvement gap of 20,48% in average.

EN :

In this paper, we consider the problem of incorporating a wide set of real-world trading constraints to the mean-variance portfolio framework. Instead of using the mean-variance model directly, we use the equivalent Mean-Absolute Deviation (MAD) linear programming formulation. The addition of the trading constraints transforms the MAD model to a mixed-integer linear programming problem. We solve both the mean-variance and MAD models with the various trading constraints using a commercial solver and find that MAD model is substantially more tractable. In addition, a heuristic is developed for the extended MAD model to provide solutions for larger problem instances.