Average case optimality

Information-based complexity studies problems where only partial and contaminated information is available. One simply states how well a problem should be solved and indicates the type of information available. The theory then yields the optimal information, the optimal algorithm, and bounds on the problem complexity. In this paper we discuss some recent results dealing with the average case setting, i.e., the setting where both the cost and the error are measured on the average.     

The case for strategic oscillation

We study a “hard” optimization problem for metaheuristic search, where a natural neighborhood (that consists of moves for flipping the values of zero-one variables) confronts two local optima, separated by a maximum possible number of moves in the feasible space. Once a descent method reaches the first local optimum, all sequences of feasible moves to reach the second, which is the global optimum, must ultimately pass through solutions that are progressively worse until reaching the worst solution of all, which is adjacent to the global optimum.     

The case for structured programming

This report is mainly a response to a paper by Henderson and Snowdon, “An Experiment in Structured Programming”. The notions of structured programming, top-down programming, and stepwise refinement are compared, and some careful guidelines for the proper use of structured programming approaches are suggested.     

Stability in the continuous case

We consider a time-invariant, finite-dimensional system of ordinary differential equations, whose right-hand side is continuous, but not Lipschitz continuous in general. For such a system, stability cannot be characterized in general by means of smooth Liapunov functions. We prove a new version of the converse of first Liapunov theorem. We give also some new conditions which allow us to verify, in different circumstances, whether a nonsmooth function is monotone along the solutions of the system.     

A case study in program transformation

A simple problem relating to binary trees is considered, and a recursive program is proved to solve this problem. The program may be transformed into a more efficient iterative one, usinggoto-statements and explicit stack handling. An independent correctness proof for this transformed version is given and compared with the original proof. Finally it is shown how a non-recursive conception of the problem may yield a structured iterative program, based onwhile-statements. A proof of this program is presented, reflecting its non-recursive conception, and it turns out that this proof has little similarity with the other two.     

Comparing Heegaard splittings -the bounded case

In a recent paper we used Cerf theory to compare strongly irreducible Heegaard splittings of the same closed irreducible orientable 3-manifold. This captures all irreducible splittings of non-Haken 3-manifolds. One application is a solution to the stabilization problem for such splittings: If are the genera of two splittings, then there is a common stabilization of genus . Here we show how to obtain similar results even when the 3-manifold has boundary.

     

Regular genus: The boundary case

Summary A particular kind of 2-cell imbedding for a class of edge-coloured graphs into surfaces with boundary is introduced and studied. This allows to define, as in [13], where the closed case was traited, a pair of invariants — the regular genus and the hole-number — for every n-manifold with boundary. These invariants are proved to coincide with the classical ones in dimension two, and to be strictly related with a Heegaard-like handlebody decomposition in dimension three. A characterization of 261-1 concludes the work.

---

Sunto Nel lavoro si introduce e si studia un nuovo tipo di immersione cellulare in superficie con bordo, per una particolare classe di grafi colorati sugli spigoli.Ciò permette, in analogia con quanto fatto nel caso chiuso in un precedente lavoro [13], di definite per ogni n-varietà con bordo una coppia di invarianti — il genere regolare ed il numero di buchi — che estendono gli omonimi concetti noti per le superficie con bordo. Di tali invarianti si studiano poi relazioni ed interpretazione geometrica, con particolare riguardo alla dimensione tre, dove essi sono collegati ad uno speciale spezzamento tipo-Heegaard.Una caratterizzazione di _n conclude il lavoro.

---

---

Work performed under the auspicies of the G.N.S.A.G.A. of the C.N.R. (National Research Council of Italy). The author was supported by the M.P.I. (Progetto Geometria delle varieta differenziabili).     

A case of the Jacobian Conjecture

H. Bass, E.H. Connell and D. Wright settled a case for the Jacobian Conjecture. In the present paper we will give another proof of the case. Project supported by the National Natural Science Foundation of China.     

Conformal restriction: The chordal case

We characterize and describe all random subsets of a given simply connected planar domain (the upper half-plane , say) which satisfy the ``conformal restriction' property, i.e., connects two fixed boundary points ( and , say) and the law of conditioned to remain in a simply connected open subset of is identical to that of , where is a conformal map from onto with and . The construction of this family relies on the stochastic Loewner evolution processes with parameter and on their distortion under conformal maps. We show in particular that SLE is the only random simple curve satisfying conformal restriction and we relate it to the outer boundaries of planar Brownian motion and SLE.     

Roots of Luzin’s case

This is a brief overview of the so-called “case of Academician Luzin” as well as the mathematical and humanitarian roots of the affair.     

Lazer-McKenna conjecture: The critical case

We consider an elliptic problem of Ambrosetti-Prodi type involving critical Sobolev exponent on a bounded smooth domain of dimension six or higher. By constructing solutions with many sharp peaks near the boundary of the domain, but not on the boundary, we prove that the number of solutions for this problem is unbounded as the parameter tends to infinity, thereby proving the Lazer-McKenna conjecture in the critical case.     

Average case analysis of DJ graphs

Sreedhar et al. [V.C. Sreedhar, G.R. Gao, Y.-F. Lee, A new framework for elimination-based data flow analysis using DJ graphs, ACM Trans. Program. Lang. Syst. 20 (2) (1998) 388–435; V.C. Sreedhar, Efficient program analysis using DJ graphs, PhD thesis, School of Computer Science, McGill University, Montréal, Québec, Canada, 1995] have presented an elimination-based algorithm to solve data flow problems. A thorough analysis of the algorithm shows that the worst-case performance is at least quadratic in the number of nodes of the underlying graph. In contrast, Sreedhar reports a linear time behavior based on some practical applications.

In this paper we prove that for goto-free programs, the average case behavior is indeed linear. As a byproduct our result also applies to the average size of the so-called dominance frontier.

A thorough average case analysis based on a graph grammar is performed by studying properties of the j-edges in DJ graphs. It appears that this is the first time that a graph grammar is used in order to analyze an algorithm. The average linear time of the algorithm is obtained by classic techniques in the analysis of algorithms and data structures such as singularity analysis of generating functions and transfer lemmas.     

Airline overbooking in the multi-class case

This paper presents an airline overbooking model at a class level for one service compartment–cabin. Class level demand data is used to determine the number of bookings that can be taken for each class. The model is optimised through the use of multi-dimensional search routines. The control level model developed is tested with data supplied by Ireland's national airline, Aer Lingus. The model shows a significant improvement over previous methods employed by Aer Lingus and was subsequently adopted by the airline.     

A period vehicle routing case study

The period vehicle routing problem is a multilevel problem assembling two classical problems: the assignment problem and the vehicle routing problem. Collection days have to be assigned to each customer and vehicle routes have to be designed for each day of the period (time horizon) so that the total distribution cost is minimised. The interaction between the temporal and spatial aspects turns the problem into one of the most challenging variations of vehicle routing. In this paper, we present the study of a real period vehicle routing system: the collection of recycling paper containers in the City Council of Almada, Portugal.