Maximum Satisfiability Problem (MAX SAT) is one of the most natural optimization problems. Since it is known to be NP-hard, approximation algorithms have been considered. The aim of this survey is to show recent developments of approximation algorithms for MAX SAT.

Given a plane graph G, we wish to find a drawing of G in the plane such that the vertices of G are represented as grid points, and the edges are represented as straight-line segments between their endpoints without any edge-intersection. Such drawings are called planar straight-line drawings of G. An additional objective is to minimize the area of the rectangular grid in which G is drawn. In this paper first we review known two methods to find such drawings, then explain a hidden relation between them, and finally survey related results.

We review public-key cryptosystems from lattice problems, which are inspired by Ajtai's remarkable result, and consider their security from the point of view of both theory and practice. We also survey recent results on the power of the lattice reduction algorithm in cryptanalysis.

The connectivity augmentation problem asks to add to a given graph the smallest number of new edges so that the edge- (or vertex-) connectivity of the graph increases up to a specified value k. The problem has been extensively studied, and several efficient algorithm have been discovered. We survey the recent development of the algorithms for this problem. In particular, we show how the minimum cut algorithm due to Nagamochi and Ibaraki is effectively applied to solve the edge-connectivity augmentation problem.

Distributed computation has attracted considerable attention and large-scale distributed systems have been designed and developed. A distributed system inherently has possibility of fault tolerance because of its redundancy. Thus, a great deal of investigation has been made to design fault-tolerant distributed algorithms. This paper introduces two promising paradigms, self-stabilization and wait-freedom, for designing fault-tolerant distributed algorithms and discusses some subjects important from the point of view of algorithm engineering.

This paper analyzes what structural features of graph problems allow efficient parallel algorithms. We survey some parallel algorithms for typical problems on three kinds of graphs, outerplanar graphs, trapezoid graphs and in-tournament graphs. Our results on the shortest path problem, the longest path problem and the maximum flow problem on outerplanar graphs, the minimum-weight connected dominating set problem and the coloring problem on trapezoid graphs and Hamiltonian path and Hamiltonian cycle problem on in-tournament graphs are adopted as working examples.

We have already proposed a process algebra µLOTOS as a mathematical framework to synthesize a process from a number of (incomplete) specifications, in which requirements for the process do not have to be completely determined. It is guaranteed that the synthesized process satisfies all the given specifications, if they are consistent. For example, µLOTOS is useful for incremental design. The advantage of µLOTOS is that liveness properties can be expressed by least fixpoints and disjunctions . In this paper, we present µLOTOSR, which is a refined µLOTOS. The improvement is that µLOTOSR has a conjunction operator . Therefore, the consistency between a number of specifications S1,,S2 can be checked by the satisfiability of the conjunction specification S1 S2. µLOTOSR does not need the complex consistency check used in µLOTOS.

This paper deals with two-processor scheduling for general acyclic SWITCH-less program nets with random node firing times. First, we introduce a hybrid priority list L* that has been shown to generate optimal schedules for the acyclic SWITCH-less program nets with unity node firing times, of which AND-nodes possess at most single input edge. Then considering the factors of existence of the AND-nodes with two input edges as well as random node firing times, we extend L* to design a new dynamic priority list Ld and four static priority lists {Lsii=1,2,3,4}; and then combining Ld and Lsi (i=1,2,3,4) we propose four hybrid priority lists {L*ii=1,2,3,4}. Finally, we apply genetic algorithm to evaluate the schedules generated by the four lists through simulations on 400 program nets. Our simulation results show two of the four lists can generate reasonably good schedules.

We first describe fundamental results about submodular functions and submodular flows, which lay a basis for devising efficient algorithms for submodular flows. We then give a comprehensive survey on algorithms for submodular flows and show some possible future research directions.

We sketch two algorithms that solve the undirected st-connectivity problem in a small amount of space. One is due to Nisan, Szemeredy and Wigderson, and takes space O(log3/2n), where n denotes the number of nodes in a give undirected graph. This is the first algorithm that overcame the Savitch barrier on the space complexity of the problem. The other is due to Tarui and this author, and takes space O(sw(G)2 log2 n), where sw(G) denotes the separation-width of a given graph G. Their result implies that the st-connectivity problem can be solved in logarithmic space for any class of graphs with separation-width bounded above by a predetermined constant. This class is one of few nontrivial classes for which the st-connectivity problem can be solved in logarithmic space.

Graph coloring is a fundamental problem, which often appears in various scheduling problems like the file transfer problem on computer networks. In this paper, we survey recent advances and results on the edge-coloring, the f-coloring, the [g,f]-coloring, and the total coloring problem for various classes of graphs such as bipartite graphs, series-parallel graphs, planar graphs, and graphs having fixed degeneracy, tree-width, genus, arboricity, unicyclic index or thickness. In particular, we review various upper bounds on the minimum numbers of colors required to color these classes of graphs, and present efficient sequential and parallel algorithms to find colorings of graphs with these numbers of colors.

The legal firing sequence problem (LFS) asks if it is possible to fire each transition some prescribed number of times in a given Petri net. It is a fundamental problem in Petri net theory as it appears as a subproblem, or as a simplified version of marking reachability, minimum initial resource allocation, liveness, and some scheduling problems. It is also known to be NP-hard, however, even under various restrictions on nets (and on firing counts), and no efficient algorithm has been previously reported for any class of nets having general edge weights. We show in this paper that LFS can be solved in polynomial time (in O(n log n) time) for a subclass of state machines, called cacti, with arbitrary edge weights allowed (if each transition is asked to be fired exactly once).

The linear complementarity problem (LCP) is one of the most widely studied mathematical programming problems. The theory of LCP can be extended to oriented matroids which are combinatorial abstractions of linear subspaces of Euclidean spaces. This paper briefly surveys the LCP, oriented matroids and algorithms for the LCP on oriented matroids.

The subject of the paper is to give an overview and latest results on the Legal Firing Sequence Problem of Petri nets (LFS for short). LFS is very fundamental in the sense that it appears as a subproblem or a simpler form of various basic problems in Petri net theory, such as the well-known marking reachability problem, the minimum initial resource allocation problem, the liveness (of level 4) problem, the scheduling problem and so on. However, solving LFS generally is not easy: it is NP -hard even for Petri nets having very simple structures. This intractability of LFS may have been preventing us from producing efficient algorithms for those problems. So research on LFS from computational complexity point of view seems to be rewarding.

There are no efficient algorithms for almost of all scheduling problems, especially when practical scheduling models are considered. Further there may be none for multi-objective scheduling problems. So we should take efforts to develope efficient approximate algorithms for multi-objective scheduling problems. The main purpose of this paper is to survey approaches to some scheduling problems from the algorithmic view points till now and investigate some hopeful approximate approaches to multiobjective scheduling problems.

A convex hull is one of the most fundamental and interesting geometric constructs in computational geometry. Considerable research effort has focused on developing algorithms, both in serial and in parallel, for computing convex hulls. In particular, there are few problems whose parallel algorithms are so thoroughly studied as convex hull problems. In this paper, we review the convex hull parallel algorithms and their paradigm. We provide a summary of results and introduce several interesting topics including typical techniques, output-size sensitive methods, randomized approaches, and robust algorithms for convex hull problems, with which we may see the highlights of the whole research for parallel algorithms. Most of our discussion uses the PRAM (Parallel Random Access Machine) computational model, but still we give a glance at the results of the other parallel computational models such as mesh, mesh-of-trees, hypercube, recofigurable array, and models of coarse grained multicomputers like BSP and LogP.

The main problem considered is submodular set cover, the problem of minimizing a linear function under a nondecreasing submodular constraint, which generalizes both well-known set cover and minimum matroid base problems. The problem is NP-hard, and two natural greedy heuristics are introduced along with analysis of their performance. As applications of these heuristics we consider various special cases of submodular set cover, including partial cover variants of set cover and vertex cover, and node-deletion problems for hereditary and matroidal properties. An approximation bound derived for each of them is either matching or generalizing the best existing bounds.

We survey recent developments in the study of approximation algorithms for NP-hard geometric optimization problems. We focus on those problems which, given a set of points, ask for a graph of a specified type on those points with the minimum total edge length, such as the traveling salesman problem, the Steiner minimum tree problem, and the k-minimum spanning tree problem. In a recent few years, several polynomial time approximation schemes are discovered for these problems. All of them are dynamic programming algorithms based on some geometric theorems that assert the existence of a good approximate solution with a simple recursive decomposition structure. Our emphasis is on these geometric theorems, which have potential uses in the design and analysis of heuristic algorithms.

In this paper, we consider the static multiprocessor scheduling problem for a class of multiprocessor systems consisting of m ( 1) identical processors connected by a complete network. The objective of this survey is to give a panoramic view of theoretical and/or practical approaches for solving the problem, that have been extensively conducted during the past three decades.

A nonlinear inverse filter is proposed for restoring signals degraded by a linear system and additive Gaussian noise. The proposed filter consists of combination of a linear high pass filter and an ε-filter, which is modified from the cascaded linear filter. The nonlinear property of the ε-filter is utilized to suppress pre-enhanced additive random noise and to restore sharp edges. It is demonstrated that the filter can be reduced to a multi-layered neural network model, and the optimal design is described by using the back propagation algorithm. The nonlinear function is approximated by a piecewise linear function, which results in simple and robust training algorithm. An application to image restoration is also presented, illustrating the effectiveness over the linear filter, especially when the amplitude of additive noise is small.