Asymptotics of number fields and the Cohen-Lenstra heuristics

We study the asymptotics conjecture of Malle for dihedral groups Dl of order 2l, where l is an odd prime. We prove the expected lower bound for those groups. For the upper bounds we show that there is a connection to class groups of quadratic number fields. The asymptotic behavior of those class groups is predicted by the Cohen-Lenstra heuristics. Under the assumption of this heuristic we are able to prove the expected upper bounds.

GRASP heuristic with path-relinking for the multi-plant capacitated lot sizing problem

This paper addresses the independent multi-plant, multi-period, and multi-item capacitated lot sizing problem where transfers between the plants are allowed. This is an NP-hard combinatorial optimization problem and few solution methods have been proposed to solve it. We develop a GRASP (Greedy Randomized Adaptive Search Procedure) heuristic as well as a path-relinking intensification procedure to find cost-effective solutions for this problem. In addition, the proposed heuristics is used to solve some instances of the capacitated lot sizing problem with parallel machines. The results of the computational tests show that the proposed heuristics outperform other heuristics previously described in the literature. The results are confirmed by statistical tests. (C) 2009 Elsevier B.V. All rights reserved.

Heuristics for the one-dimensional cutting stock problem with limited multiple stock lengths

This paper deals with the classical one-dimensional integer cutting stock problem, which consists of cutting a set of available stock lengths in order to produce smaller ordered items. This process is carried out in order to optimize a given objective function (e.g., minimizing waste). Our study deals with a case in which there are several stock lengths available in limited quantities. Moreover, we have focused on problems of low demand. Some heuristic methods are proposed in order to obtain an integer solution and compared with others. The heuristic methods are empirically analyzed by solving a set of randomly generated instances and a set of instances from the literature. Concerning the latter. most of the optimal solutions of these instances are known, therefore it was possible to compare the solutions. The proposed methods presented very small objective function value gaps. (C) 2008 Elsevier Ltd. All rights reserved.

Fast heuristics for the Steiner tree problem with revenues, budget and hop constraints

This article describes and compares three heuristics for a variant of the Steiner tree problem with revenues, which includes budget and hop constraints. First, a greedy method which obtains good approximations in short computational times is proposed. This initial solution is then improved by means of a destroy-and-repair method or a tabu search algorithm. Computational results compare the three methods in terms of accuracy and speed. (C) 2007 Elsevier B.V. All rights reserved.

Towards universal and statistical-driven heuristics for automatic classification of sports video events

Researchers worldwide have been actively seeking for the most robust and powerful solutions to detect and classify key events (or highlights) in various sports domains. Most approaches have employed manual heuristics that model the typical pattern of audio-visual features within particular sport events To avoid manual observation and knowledge, machine-learning can be used as an alternative approach. To bridge the gaps between these two alternatives, an attempt is made to integrate statistics into heuristic models during highlight detection in our investigation. The models can be designed with a modest amount of domain-knowledge, making them less subjective and more robust for different sports. We have also successfully used a universal scope of detection and a standard set of features that can be applied for different sports that include soccer, basketball and Australian football. An experiment on a large dataset of sport videos, with a total of around 15 hours, has demonstrated the effectiveness and robustness of our
aIlgorithms.

Using decision-tree to automatically construct learned-heuristics for events classification in sports video

Automatic events classification is an essential requirement for constructing an effective sports video summary. It has become a well-known theory that the high-level semantics in sport video can be “computationally interpreted” based on the occurrences of specific audio and visual features which can be extracted automatically. State-of-the-art solutions for features-based event classification have only relied on either manual-knowledge based heuristics or machine learning. To bridge the gaps, we have successfully combined the two approaches by using learning-based heuristics. The heuristics are constructed automatically using decision tree while manual supervision is only required to check the features and highlight contained in each training segment. Thus, fully automated construction of classification system for sports video events has been achieved. A comprehensive experiment on 10 hours video dataset, with five full-match soccer and five full-match basketball videos, has demonstrated the effectiveness/robustness of our algorithms.

Agent-based heuristics to solve NP-hard scheduling problems

A novel agent-driven heuristic approach was developed to control the operational scheduling for a local manufacturer. This approach outperformed the traditional kanban control mechanism under numerous simulated benchmarking tests. Using this approach, the individual machine loading was reduced by, on average, 28%, with the loading spread reduced by 85%