On the construction of samples for testing approximate optimization methods for estimate calculation algorithms

To validate approximate optimization schemes for estimate calculation algorithms (ECAs), it is necessary to compute the optimal height, which cannot be done in a reasonable amount of time. A variety of samples are built for which the optimal height of the ECAs is known by construction.     

Speedup estimates for some variants of the parallel implementations of the branch-and-bound method

The efficiency of parallel implementations of the branch-and-bound method in discrete optimization problems is considered. A theoretical analysis and comparison of two parallel implementations of this method is performed. A mathematical model of the computation process is constructed and used to obtain estimates of the maximum possible speedup. Examples of problems in which none of these two parallel implementations can speed up the computations are considered.     

现代优化计算方法在蛋白质结构预测中的应用

现代优化计算方法在蛋白质结构预测中占有重要地位.简要地介绍了模拟退火算法,遗传算法,人工神经网络和图论算法在蛋白质结构预测中的应用.对国内外近年来应用这些算法,特别是在蛋白质构象搜索问题中,解决蛋白质结构预测的研究作了回顾,并分析、比较了这几种算法的效果和特点.     

A polynomial algorithm for one problem of guillotine cutting

We consider the problem of guillotine cutting a rectangular sheet into two rectangular pieces without rotations. The question is whether there exists a cutting pattern with given numbers of occurrences of both rectangular pieces. A polynomial time algorithm is described to construct the convex hull of solutions to this problem.     

Analysis of Decomposition Algorithms with Benders Cuts for p-Median Problem

In this paper the algorithms for solving the p-median problem based on the Benders decomposition are investigated. A family of problems hard for solving with such algorithms is constructed and then generalized to a special NP-hard case of the p-median problem. It is shown that the effectiveness of the considered algorithms depends on the choice of the optimal values of the dual variables used in Benders cuts. In particular, the depth of the cuts can be equal to one.     

Combining Swaps and Node Weights in an Adaptive Greedy Approach for the Maximum Clique Problem

In this work, the NP-hard maximum clique problem on graphs is considered. Starting from basic greedy heuristics, modifications and improvements are proposed and combined in a two-phase heuristic procedure. In the first phase an improved greedy procedure is applied starting from each node of the graph; on the basis of the results of this phase a reduced subset of nodes is selected and an adaptive greedy algorithm is repeatedly started to build cliques around such nodes. In each restart the selection of nodes is biased by the maximal clique generated in the previous execution. Computational results are reported on the DIMACS benchmarks suite. Remarkably, the two-phase procedure successfully solves the difficult Brockington-Culberson instances, and is generally competitive with state-of-the-art much more complex heuristics.     

Intercomparison of retrieval codes used for the analysis of high-resolution, ground-based FTIR measurements

A rigorous and systematic intercomparison of codes used for the retrieval of trace gas profiles from high-resolution ground-based solar absorption FTIR measurements is presented for the first time. Spectra were analyzed with the two widely used independent, retrieval codes: SFIT2 and PROFFIT9. Vertical profiles of O₃, HNO₃, HDO, and N₂O were derived from the same set of typical observed spectra. Analysis of O₃ was improved by using updated line parameters. It is shown that profiles and total column amounts are in excellent agreement, when similar constraints are applied, and that the resolution kernel matrices are also consistent. Owing to the limited altitude resolution of ground-based observations, the impact of the constraints on the solution is not negligible. It is shown that the results are also compatible for independently chosen constraints. Perspectives for refined constraints are discussed. It can be concluded that the error budget introduced by the radiative transfer code and the retrieval algorithm on total columns deduced from high-resolution ground-based solar FTIR spectra is below 1%.     

Randomization helps to perform independent tasks reliably

This paper is about algorithms that schedule tasks to be performed in a distributed failure‐prone environment, when processors communicate by message‐passing, and when tasks are independent and of unit length. The processors work under synchrony and may fail by crashing. Failure patterns are imposed by adversaries. Linearly‐bounded adversaries may fail up to a constant fraction of the processors. Weakly‐adaptive adversaries have to select, prior to the start of an execution, a subset of processors to be failure‐prone, and then may fail only the selected processors, at arbitrary steps, in the course of the execution. Strongly adaptive adversaries have a total number of failures as the only restriction on failure patterns. The measures of complexity are work, measured as the available processor steps, and communication, measured as the number of point‐to‐point messages. A randomized algorithm is developed, that attains both ??(n log*n) expected work and ??(n log*n) expected communication, against weakly‐adaptive linearly‐bounded adversaries, in the case when the numbers of tasks and processors are both equal to n. This is in contrast with performance of algorithms against strongly‐adaptive linearly‐bounded adversaries, which has to be Ω(n log n/log log n) in terms of work. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 2004     

On the advantage over a random assignment

We initiate the study of a new measure of approximation. This measure compares the performance of an approximation algorithm to the random assignment algorithm. This is a useful measure for optimization problems where the random assignment algorithm is known to give essentially the best possible polynomial time approximation. In this paper, we focus on this measure for the optimization problems Max‐Lin‐2 in which we need to maximize the number of satisfied linear equations in a system of linear equations modulo 2, and Max‐k‐Lin‐2, a special case of the above problem in which each equation has at most k variables. The main techniques we use, in our approximation algorithms and inapproximability results for this measure, are from Fourier analysis and derandomization. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2004