We introduce a novel, efficient computational method, ZEUS, for numerical optimization, and provide an open-source implementation. It has four key ingredients: (1) particle swarm optimization (PSO), (2) the use of the Broyden-Fletcher-Goldfarb-Shanno (BFGS) method, (3) automatic differentiation (AD), and (4) GPUs. Our approach addresses the computational challenges inherent in high-dimensional, non-convex optimization problems. In the first phase of the algorithm, we get a potentially good set of starting points using PSO. Thereafter, we run BFGS independently in parallel from these starting points. BFGS is one of the bestperforming algorithms for numerical optimization. However, it requires the gradient of the function being optimized. ZEUS integrates automatic differentiation into BFGS thus avoiding the need for the user to calculate derivatives explicitly. The use of GPUs allows ZEUS to speed up the calculations substantially. We carry out systematic studies to explore the trade-offs between the number of PSO iterations taken, starting points, and BFGS iteration depth. We show that a handful of iterations of PSO can improve global convergence when combined with BFGS. We also present performance studies using common test functions. The source code can be found at https://github.com/fnal-numerics/global-optimizer-gpu.

Many scientific and engineering applications require repeated calculations of derivatives of output functions with respect to input parameters. Automatic Differentiation (AD) is a method that automates derivative calculations and can significantly speed up code development. In Computational Fluid Dynamics (CFD), derivatives of flux functions with respect to state variables (Jacobian) are needed for efficient solutions of the nonlinear governing equations. AD of flux functions on graphics processing units (GPUs) is challenging as flux computations involve many intermediate variables that create high register pressure and require significant memory traffic because of the need to store the derivatives. This paper presents a forward-mode AD method based on multivariate dual numbers that addresses these challenges and simultaneously reduces the floating-point operation count. The dimension of the multivariate dual numbers is optimized for performance. The flux computations are restructured to minimize the number of temporary variables and reduce register pressure. For effective utilization of memory bandwidth, shared memory is used to store the local flux Jaco-bian. This AD implementation is compared with several other Jacobian implementations on an NVIDIA V100 GPU (V100). For three-dimensional perfect-gas compressible-flow equations implemented in a practical CFD code, the AD implementation of a flux Jacobian based on multivariate dual numbers of dimension 5 outperforms all other GPU AD implementations on V100. Its performance is comparable with the optimized hand-differentiated version. The implementation achieves 75% of the peak floating-point throughput and 61 % of the peak global device memory bandwidth usage.

BACKGROUND: Human subtelomeric DNA regulates the length and stability of adjacent telomeres that are critical for cellular function, and contains many gene/pseudogene families. Large evolutionarily recent segmental duplications and associated structural variation in human subtelomeres has made complete sequencing and assembly of these regions difficult to impossible for many loci, complicating or precluding a wide range of genetic analyses to investigate their function. RESULTS: We present a hybrid assembly method, NanoPore Guided REgional Assembly Tool (NPGREAT), which combines Linked-Read data with mapped ultralong nanopore reads spanning subtelomeric segmental duplications to potentially overcome these difficulties. Linked-Read sets of DNA sequences identified by matches with 1-copy subtelomere sequence adjacent to segmental duplications are assembled and extended into the segmental duplication regions using Regional Extension of Assemblies using Linked-Reads (REXTAL). Mapped telomere-containing ultralong nanopore reads are then used to provide contiguity and correct orientation for matching REXTAL sequence contigs as well as identification/correction of any misassemblies. Our method was tested for a subset of representative subtelomeres with ultralong nanopore read coverage in the haploid human cell line CHM13. A 10X Linked-Read dataset from CHM13 was combined with ultralong nanopore reads from the same genome to provide improved subtelomere assemblies. Comparison of Nanopore-only assemblies using SHASTA with our NPGREAT assemblies in the distal-most subtelomere regions showed that NPGREAT produced higher-quality and more complete assemblies than SHASTA alone when these regions had low ultralong nanopore coverage (such as cases where large segmental duplications were immediately adjacent to (TTAGGG) tracts). CONCLUSION: In genomic regions with large segmental duplications adjacent to telomeres, NPGREAT offers an alternative economical approach to improving assembly accuracy and coverage using linked-read datasets when more expensive HiFi datasets of 10-20 kb reads are unavailable.

We present a new adaptive parallel algorithm for the challenging problem of multi-dimensional numerical integration on massively parallel architectures. Adaptive algorithms have demonstrated the best performance, but efficient many-core utilization is difficult to achieve because the adaptive work-load can vary greatly across the integration space and is impossible to predict a priori. Existing parallel algorithms utilize sequential computations on independent processors, which results in bottlenecks due to the need for data redistribution and processor synchronization. Our algorithm employs a high-throughput approach in which all existing sub-regions are processed and sub-divided in parallel. Repeated sub-region classification and filtering improves upon a brute-force approach and allows the algorithm to make efficient use of computation and memory resources. A CUDA implementation shows orders of magnitude speedup over the fastest open-source CPU method and extends the achievable accuracy for difficult integrands. Our algorithm typically outperforms other existing deterministic parallel methods.

Genomic regions of high segmental duplication content and/or structural variation have led to gaps and misassemblies in the human reference sequence, and are refractory to assembly from whole-genome short-read datasets. Human subtelomere regions are highly enriched in both segmental duplication content and structural variations, and as a consequence are both impossible to assemble accurately and highly variable from individual to individual. Recently, we developed a pipeline for improved region-specific assembly called Regional Extension of Assemblies Using Linked-Reads (REXTAL). In this study, we evaluate REXTAL and genome-wide assembly (Supernova) approaches on 10X Genomics linked-reads data sets partitioned and barcoded using the Gel Bead in Emulsion (GEM) microfluidic method. Our results describe the accuracy and relative performance of these two approaches using the reference-based assessment module of QUAST. We show that REXTAL dramatically outperforms the Supernova whole genome assembler in subtelomeric segmental duplication regions, and results in highly accurate assemblies. Nearly all of the REXTAL "misassemblies" identified using default QUAST parameters simply pinpoint locations of tandem repeat arrays in the reference sequence where the repeat array length differs from that in the cognate REXTAL assembly by 1000 bp.

Human subtelomere regions are highly enriched in large segmental duplications and structural variants, leading to many gaps and misassemblies in these regions. We develop a novel method, NPGREAT (NanoPore Guided REgional Assembly Tool), which combines Nanopore ultralong read datasets and short-read assemblies derived from 10x linked-reads to efficiently assemble these subtelomere regions into a single continuous sequence. We show that with the use of ultralong Nanopore reads as a guide, the highly accurate shorter linked-read sequence contigs are correctly oriented, ordered, spaced and extended. In the rare cases where a linked-read sequence contig contains inaccurately assembled segments, the use of Nanopore reads allows for detection and correction of this error. We tested NPGREAT on four representative subtelomeres of the NA12878 human genome (10p, 16p, 19q and 20p). The results demonstrate that the final computed assembly of each subtelomere is accurate and complete.

Particle colliders are essential tools in the pursuit of understanding matter interactions in the universe. The tremendous cost of their operation and requirement for finetuning, make high-fidelity particle collider simulations essential in ensuring optimal operation. Simulations of the beam-beam effects of colliding particle bunches are extremely time-consuming since they include hundreds of billions of particles that collide millions of times per second. A high degree of parallelization is required to decrease the execution time of such simulations. GPUs present an opportunity towards making such simulations viable, though several challenges must be overcome in order to achieve efficient parallelization. One major challenge addressed in this paper is an efficient simulation of multiple bunch collision on a cluster of GPUs. The numerous colliding bunches are subject to scheduling constraints, which requires the utilization of an efficient collision schedule algorithm, all the while ensuring that the processors are not underutilized and communication overheads are low. We implemented two schemes on a 8-node cluster with four K40 GPUs on each node for a total of 32 GPUs. We demonstrated an almost linear speedup for large bunches with the number of GPUs.

Parallel computing architectures like GPUs have traditionally been used to accelerate applications with dense and highly-structured workloads; however, many important applications in science and engineering are irregular and dynamic in nature, making their effective parallel implementation a daunting task. Numerical simulation of charged particle beam dynamics is one such application where the distribution of work and data in the accurate computation of collective effects at each time step is irregular and exhibits control-flow and memory access patterns that are not readily amenable to GPU's architecture. Algorithms with these properties tend to present both significant branch and memory divergence on GPUs which leads to severe performance bottlenecks.We present a novel cache-aware algorithm that uses machine learning to address this problem. The algorithm presented here uses supervised learning to adaptively model and track irregular access patterns in the computation of collective effects at each time step of the simulation to anticipate the future control-flow and data access patterns. Access pattern forecast are then used to formulate runtime decisions that minimize branch and memory divergence on GPUs, thereby improving the performance of collective effects computation at a future time step based on the observations from earlier time steps. Experimental results on NVIDIA Tesla K40 GPU shows that our approach is effective in maximizing data reuse, ensuring workload balance among parallel threads, and in minimizing both branch and memory divergence. Further, the parallel implementation delivers up to 485 Gflops of double precision performance, which translates to a speedup of up to 2.5X compared to the fastest known GPU implementation.

A key idea in de novo modeling of a medium-resolution density image obtained from cryo-electron microscopy is to compute the optimal mapping between the secondary structure traces observed in the density image and those predicted on the protein sequence. When secondary structures are not determined precisely, either from the image or from the amino acid sequence of the protein, the computational problem becomes more complex. We present an efficient method that addresses the secondary structure placement problem in presence of multiple secondary structure predictions and computes the optimal mapping. We tested the method using 12 simulated images from α-proteins and two Cryo-EM images of α-β proteins. We observed that the rank of the true topologies is consistently improved by using multiple secondary structure predictions instead of a single prediction. The results show that the algorithm is robust and works well even when errors/misses in the predicted secondary structures are present in the image or the sequence. The results also show that the algorithm is efficient and is able to handle proteins with as many as 33 helices.

Cryo-electron microscopy is a fast emerging biophysical technique for structural determination of large protein complexes. While more atomic structures are being determined using this technique, it is still challenging to derive atomic structures from density maps produced at medium resolution when no suitable templates are available. A critical step in structure determination is how a protein chain threads through the 3-dimensional density map. A dynamic programming method was previously developed to generate K best matches of secondary structures between the density map and its protein sequence using shortest paths in a related weighted graph. We discuss challenges associated with the creation of the weighted graph and explore heuristic methods to solve the problem of matching secondary structures.

Accurate simulation of collective effects in electron beams is one of the most challenging and computationally intractable problems in accelerator physics. More recently, researchers have developed a GPU-accelerated, high-fidelity simulation of electron beam dynamics that models the collective effects much more accurately. The simulation, however, is heavily data-intensive and memory-bound. In particular, data-dependent, irregular memory access patterns and control-flow in the collective effects computation phase of the simulation leads to a large number of non-coalesced memory accesses on the GPU. This significantly deteriorates the overall performance. Moreover, the parallel simulation exhibits poor data locality. This, together with non-coalesced memory accesses, leads to ineffective use of the memory hierarchy. We present a novel cache-aware algorithm that uses a locality heuristic to maximize data reuse by improving data locality. Additionally, the algorithm uses a control-flow heuristic to balance the workload among threads. The control-flow heuristic also minimizes threads divergence and enables reuse of partial results of previous iterations and thereby reducing the overall operation count. Experimental results on NVIDIA Tesla K40 GPU shows that our approach delivers up to 450 Gflops of double precision performance, which translates to a speedup of up to 16X compared with the current state-of-the-art GPU implementation.

MOTIVATION: Insertion sequences (ISs) are transposable elements present in most bacterial and archaeal genomes that play an important role in genomic evolution. The increasing availability of sequenced prokaryotic genomes offers the opportunity to study ISs comprehensively, but development of efficient and accurate tools is required for discovery and annotation. Additionally, prokaryotic genomes are frequently deposited as incomplete, or draft stage because of the substantial cost and effort required to finish genome assembly projects. Development of methods to identify IS directly from raw sequence reads or draft genomes are therefore desirable. Software tools such as Optimized Annotation System for Insertion Sequences and IScan currently identify IS elements in completely assembled and annotated genomes; however, to our knowledge no methods have been developed to identify ISs from raw fragment data or partially assembled genomes. We have developed novel methods to solve this computationally challenging problem, and implemented these methods in the software package ISQuest. This software identifies bacterial ISs and their sequence elements-inverted and direct repeats-in raw read data or contigs using flexible search parameters. ISQuest is capable of finding ISs in hundreds of partially assembled genomes within hours, making it a valuable high-throughput tool for a global search of IS elements. We tested ISQuest on simulated read libraries of 3810 complete bacterial genomes and plasmids in GenBank and were capable of detecting 82% of the ISs and transposases annotated in GenBank with 80% sequence identity. CONTACT: [email protected].

The k-core of a graph is the largest induced subgraph with minimum degree k. The k-core decomposition is to find the core number of each vertex in a graph, which is the largest value of k that the vertex belongs to a k-core. k-core decomposition has applications in many areas including network analysis, computational biology and graph visualization. The primary reason for it being widely used is the availability of an O(n + m) algorithm. The algorithm was proposed by Batagelj and Zaversnik and is considered the state-of-the-art algorithm for k-core decomposition. However, the algorithm is not suitable for parallelization and to the best of our knowledge there is no algorithm proposed for k-core decomposition on multicore processors. Also, the algorithm has not been experimentally analyzed for large graphs. Since the working set size of the algorithm is large, and the access pattern is highly random, it can be inefficient for large graphs. In this paper, we present an experimental analysis of the algorithm of Batagelj and Zaversnik and propose a new algorithm, ParK, that significantly reduces the working set size and minimizes the random accesses. We provide an experimental analysis of the algorithm using graphs with up to 65 million vertices and 1.8 billion edges. We compare the ParK algorithm with state-of-the-art algorithm and show that it is up to 6 times faster. We also provide a parallel methodology and show that the algorithm is amenable to parallelization on multicore architectures. We ran our experiments on a 4 socket Nehalem-EX processor which has 8 cores per socket and show that the algorithm scales up to 21 times using 32 cores.

Maximal clique enumeration (MCE) is a fundamental problem in graph theory. It plays a vital role in many network analysis applications and in computational biology. MCE is an extensively studied problem. Recently, Eppstein et al. proposed a state-of-the-art sequential algorithm that uses degeneracy based ordering of vertices to improve the efficiency. In this paper, we propose a new parallel implementation of the algorithm of Eppstein et al. using a new bit-based data structure. The new data structure not only reduces the working set size significantly but also by enabling the use of bit-parallelism improves the performance of the algorithm. We illustrate the significance of degeneracy ordering in load balancing and experimentally evaluate the impact of scheduling on the performance of the algorithm. We present experimental results on several types of synthetic and real-world graphs with up to 50 million vertices and 100 million edges. We show that our approach outperforms Eppstein et al.'s approach by up to 4 times and also scales up to 29 times when run on a multicore machine with 32 cores.

Electron cryomicroscopy is becoming a major experimental technique in solving the structures of large molecular assemblies. More and more three-dimensional images have been obtained at the medium resolutions between 5 and 10 Å. At this resolution range, major α-helices can be detected as cylindrical sticks and β-sheets can be detected as plain-like regions. A critical question in de novo modeling from cryo-EM images is to determine the match between the detected secondary structures from the image and those on the protein sequence. We formulate this matching problem into a constrained graph problem and present an O(Δ(2)N(2)2(N)) algorithm to this NP-Hard problem. The algorithm incorporates the dynamic programming approach into a constrained K-shortest path algorithm. Our method, DP-TOSS, has been tested using α-proteins with maximum 33 helices and α-β proteins up to five helices and 12 β-strands. The correct match was ranked within the top 35 for 19 of the 20 α-proteins and all nine α-β proteins tested. The results demonstrate that DP-TOSS improves accuracy, time and memory space in deriving the topologies of the secondary structure elements for proteins with a large number of secondary structures and a complex skeleton.

We present a memory-efficient algorithm and its implementation for solving multidimensional numerical integration on a cluster of compute nodes with multiple GPU devices per node. The effective use of shared memory is important for improving the performance on GPUs, because of the bandwidth limitation of the global memory. The best known sequential algorithm for multidimensional numerical integration CUHRE uses a large dynamic heap data structure which is accessed frequently. Devising a GPU algorithm that caches a part of this data structure in the shared memory so as to minimizes global memory access is a challenging task. The algorithm presented here addresses this problem. Furthermore we propose a technique to scale this algorithm to multiple GPU devices. The algorithm was implemented on a cluster of Intel®Xeon®CPU X5650 compute nodes with 4 Tesla M2090 GPU devices per node. We observed a speedup of up to 240 on a single GPU device as compared to a speedup of 70 when memory optimization was not used. On a cluster of 6 nodes (24 GPU devices) we were able to obtain a speedup of up to 3250. All speedups here are with reference to the sequential implementation running on the compute node.

Recent development in Graphics Processing Units (GPUs) has enabled a new possibility for highly efficient parallel computing in science and engineering. Their massively parallel architecture makes GPUs very effective for algorithms where processing of large blocks of data can be executed in parallel. Multidimensional integration has important applications in areas like computational physics, plasma physics, computational fluid dynamics, quantum chemistry, molecular dynamics and signal processing. The computationally intensive nature of multidimensional integration requires a high-performance implementation. In this study, we present an efficient deterministic parallel algorithm for adaptive multidimensional numerical integration on GPUs. Various optimization techniques are applied to maximize the utilization of the GPU. GPU-based implementation outperforms the best known sequential methods and achieves a speed-up of up to 100. It also shows good scalability with the increase in dimensionality.

SUMMARY In this paper, we present an efficient, easily parallelizable approach to solve planted motif problem (PMP). PMP is a well‐studied problem in computational biology. It is useful in developing methods for finding transcription factor binding sites, classifying sequences, and building phylogenetic trees. Many approaches to solve PMP can be found in the literature. But the problem with those approaches is that they are difficult to parallelize as they have been designed for serial computers. In this paper, we propose a simple, easily parallelizable enumeration‐based approach called BitBased. As with most other enumeration‐based approaches that have been proposed to solve PMP, BitBased is also limited by memory for solving large‐sized problems. To overcome this limitation, we propose various modifications, which not only reduce the memory requirement but also improve the performance of the approach. We have implemented our approach on multicore and GPU devices. We found that BitBased outperforms all the approaches proposed to solve PMP so far. BitBased is able to solve the (21,8) instance, which was not previously reported as solved in the literature. Copyright © 2012 John Wiley & Sons, Ltd.

The determination of the secondary structure topology is a critical step in deriving the atomic structure from the protein density map obtained from electron cryo-microscopy technique. This step often relies on the matching of two sources of information. One source comes from the secondary structures detected from the protein density map at the medium resolution, such as 5-10 A. The other source comes from the predicted secondary structures from the amino acid sequence. Due to the uncertainty in either source of information, a pool of possible secondary structure positions has to be sampled in order to include the true answer. A naive way to find the native topology is to exhaustively map the pool of possible secondary structures detected in the density map with the pool of the secondary structures predicted from the sequence and search for the topology with the lowest cost. This paper studies the question that is how to reduce the computation of the mapping when the uncertainty of the secondary structure predictions is considered. We present a method that combines the concept of dynamic graph with our previous work of using constrained shortest path to identify the topology of the secondary structures. We show a reduction of about 34.55% time as comparison to the naive way of handling the inaccuracies. To our knowledge, this is the Is computationally effective exact algorithm to identify the optimal topology of the secondary structures when the inaccuracy of the predicted data is considered.

The session will introduce participants to curricular modules (projects) based entirely on primary historical source material, developed by an interdisciplinary team of seven computer science and mathematical sciences faculty at New Mexico State

In silico characterization of promoter or regulatory regions of genomes is an important aspect of understanding gene expression regulation. Plant secondary metabolism represents an opportunity to discover promoter elements among coordinately transcribed genes on these complex pathways. We used CisFind, a software tool we developed, for finding un-extendable conserved matches among multiple DNA sequences. The underlying algorithm for this tool is a modified suffix tree. We used CisFind to detect unknown common regulatory elements in the 5' proximal regions of four genes on the capsaicinoid biosynthetic pathway. These DNA sequences were retrieved by genome walking from eight different chili peppers differing in pungency levels; tomato DNA was included as an outgroup. Nine unique candidate promoter elements were identified among these sequences. Their distribution is consistent with a role in regulating these genes for expression related to chili pungency. These candidate promoter elements were also predicted by other online software tools with different algorithms, increasing the probability that these elements are in fact biologically relevant.

We discuss a project based on an original source from 1838 by Gabriel Lamé, which was used to teach dynamic programming in an Algorithms and Data Structures course for junior level computer science students. The project was developed as part of a group effort at New Mexico State University on using original historical sources in teaching. The project is based on an excerpt from a letter of Monsieur Lamé to Monsieur Liouville on the question: Given a convex polygon, in how many ways can one partition it into triangles by means of diagonals? A variety of tasks in the project, which includes reading, writing, proving statements by mathematical induction, deriving formulas, writing computer programs and analyzing and comparing them for efficiency, help students to develop verbal, analytical and discrete mathematics skills necessary for computer science. We also discuss student reactions to the project and to learning from historical sources.

We present faster sequential and parallel algorithms for computing the solvent accessible surface area (ASA) of protein molecules. The ASA is computed by finding the exposed surface areas of the spheres obtained by increasing the van der Waals radii of the atoms with the van der Waals radius of the solvent. Using domain specific knowledge, we show that the number of sphere intersections is only O(n), where n is the number of atoms in the protein molecule. For computing sphere intersections, we present hash-based algorithms that run in O(n) expected sequential time and O(n/p) expected parallel time and sort-based algorithms that run in worst-case O(n log n) sequential time and O(n log n/p) parallel time. These are significant improvements over previously known algorithms which take O(n/sup 2/) time sequentially and O(n/sup 2//p) time in parallel. We present a Monte Carlo algorithm for computing the solvent accessible surface area. The basic idea is to generate points uniformly at random on the surface of spheres obtained by increasing the van der Waals radii of the atoms with the van der Waals radius of the solvent molecule and to test the points for accessibility. We also provide error bounds as a function of the sample size. Experimental verification of the algorithms is carried out using an IBM SP-2.

The Random Oracle Hypothesis, attributed to Bennett and Gill, essentially states that the relationships between complexity classes which hold for almost all relativized worlds must also hold in the unrelativized case. Although this paper is not the first to provide a counterexample to the Random Oracle Hypothesis, it does provide a most compelling counterexample by showing that for almost all oracles A, IPA ≠ PSPACEA. If the Random Oracle Hypothesis were true, it would contradict Shamir's result that IP = PSPACE. In fact, it is shown that for almost all oracles A, co-NPA ⫋ IPA. These results extend to the multiprover proof systems of Ben-Or, Goldwasser, Killian, and Wigderson. In addition, this paper shows that the Random Oracle Hypothesis is sensitive to small changes in the definition. A class IPP, similar to IP, is defined. Surprisingly, the IPP = PSPACE result holds for all oracle worlds.

We investigate the relationship between logical expressibility of NP optimization problems and their approximation properties. First such attempt was made by Papadimitrou and Yannakakis (1988), who defined the class of NPO problems MAX NP. We show that many important optimization problems do not belong to MAX NP and that, in fact, there are problems in P which are not in MAX NP. The problems that we consider fit naturally in a new complexity class that we call MAX Π1. We prove that several natural optimization problems are complete for MAX Π1 under approximation-preserving reductions. All these complete problems are not approximable unless P = NP. This motivates the definition of subclasses of MAX Π1 that only contain problems which are presumably eaiser with respect to approximation. In particular, the class that we call RMAX(2) contains approximable problems and problems like MAX CLIQUE that are not known to be nonapproximable. We prove the MAX CLIQUE and several other optimization problems are complete for RMAX(2). All the complete problems in RMAX(2) share the interesting property that they either are nonapproximable or are approximable to any degree of accuracy.

In this paper we review the key results about space bounded complexity classes, discuss the central open problems and outline the prominent proof techniques. We show that, for a slightly modified Turing machine model, low level deterministic and nondeterministic space bounded complexity classes are different. Furthermore, for this computation model, we show that Savitch's theorem and the Immerman-Szelepcsényi theorem do not hold in the range lg lg n to lg n. We also present other changes in the computation model which bring out and clarify the importance of space constructibility. We conclude by enumerating open problems which arise out of the discussion.

We investigate tile relationship between logical expressibility of NP optimization problems and their approximation properties.First sucll attempt was made by Papadimitriou and Yannakakis, who defined the class of NPO problems MAX NP.We show that many importaut optimization problems do not belong to MAX NP and that in fact there are problems in P which are not ill lk'IAX NP.The problems that we consider fit naturally in a new complexity class that we call MAX Ill.We prove that several natural optimization problems are complete for MAX H1 under approxima.tionpreserving reductions.All these complete problems are non approximable unless P ¢ NP.This motivates the definition of subclasses of MAX II1 that only contain problems which are presumably easier with respect to approximation.In particular, the class that we call RMAX(2), contains approximable problems and prob-]elllS like MAX CLIQUE that are not known to be nonapproximable.We prove that MAX CLIQUE and several other optimization problems are complete for RMAX(2).