On the identification of degenerate indices in the nonlinear complementarity problem with the proximal point algorithm

In this paper we focus on the problem of identifying the index sets P(x):=i|x_i>0, N(x):={i|F_i(x)>0 and C(x):=i|x_i=F_i(x)=0} for a solution x of the monotone nonlinear complementarity problem NCP(F). The correct identification of these sets is important from both theoretical and practical points of view. Such an identification enables us to remove complementarity conditions from the NCP and locally reduce the NCP to a system which can be dealt with more easily. We present a new technique that utilizes a sequence generated by the proximal point algorithm (PPA). Using the superlinear convergence property of PPA, we show that the proposed technique can identify the correct index sets without assuming the nondegeneracy and the local uniqueness of the solution.This work was supported in part by a Grant-in-Aid for Scientific Research from the Ministry of Education, Science, Sports and Culture of Japan.Mathematics Subject Classification (2000): 90C33, 65K10     

A remark on the Riemann‐Hilbert problem with a vanishing coefficient

This paper concerns the existence of nontrivial solutions of the Riemann‐Hilbert problem with a continuous coefficient whose values belong to two rays in the complex plane. Our results extend those recently obtained by E. Shargorodsky and J. F. Toland [6]. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

A branch and bound algorithm for the robust shortest path problem with interval data

Many real problems can be modelled as robust shortest path problems on interval digraphs, where intervals represent uncertainty about real costs and a robust path is not too far from the shortest path for each possible configuration of the arc costs.A branch and bound algorithm for this problem is presented.     

Local approximations for maximum partial subgraph problem

We deal with MAXH₀-FREE PARTIAL SUBGRAPH. We mainly prove that 3-locally optimum solutions achieve approximation ratio (δ₀+1)/(B+2+ν₀), where B=max_v∈Vd_G(v), δ₀=min_v∈V(H0)d_H0(v) and ν₀=(|V(H₀)|+1)/δ₀. Next, we show that this ratio rises up to 3/(B+1) when H₀=K₃. Finally, we provide hardness results for MAXK₃-FREE PARTIAL SUBGRAPH.     

Sufficient conditions of non‐uniqueness for the Coulomb friction problem

We consider the Signorini problem with Coulomb friction in elasticity. Sufficient conditions of non‐uniqueness are obtained for the continuous model. These conditions are linked to the existence of real eigenvalues of an operator in a Hilbert space. We prove that, under appropriate conditions, real eigenvalues exist for a non‐local Coulomb friction model. Finite element approximation of the eigenvalue problem is considered and numerical experiments are performed. Copyright © 2003 John Wiley & Sons, Ltd.     

Some non‐standard problems in viscous flow

Energy bounds are derived for Dirichlet type boundary value problems for the Navier–Stokes and Stokes equations when a combination of the solution values initially and at a later time is prescribed. The bounds are obtained by means of a differential inequality and imply uniqueness and continuous data dependence of the solutions for a range of values of the parameter in the non‐standard auxiliary condition. Copyright © 2004 John Wiley & Sons, Ltd.     

Two-Frequency Autowave Processes in the Complex Ginzburg–Landau Equation

We study the complex Ginzburg–Landau equation with zero Neumann boundary conditions on a finite interval and establish that this boundary problem (with suitably chosen parameters) has countably many stable two-dimensional self-similar tori. The case of periodic boundary conditions is also investigated.     

匹配问题实例空间和解空间结构

本文通过研究匹配问题的实例空间，匈牙利算法和解空间三者之间的关系，指出S实例空间的数目与问题复杂度之间的关系既不是充分也不是必要的，而如何对问题的解空间进行合理的分解才能是问题的关键。     

3-正则图的分割问题是NP-完全问题

证明了3-正则图的最小平分问题和最小α-分割问题都是NP-完全问题.     

Degenerate nonlinear hyperbolic conservation laws: Non classical geometrical theory

Kinetic selection principles have been shown to be useful and physically reasonable in nonlinear hyperbolic problems with large amplitude phase transitions. We refer to Abeyaratne and Knowles, [A-K], for discussion on the subject. They also have been used for degenerate nonlinear problems, where the genuine nonlinearity property of Lax is violated. This is the framework of Liu, [Li], in the kinetic situation of Hayes and Le Floch, [H-L], where their so-called non classical shocks may be seen as small amplitude phase transitions. Here, we describe the local geometry generated by the generic non genuinely nonlinear assumption. A geometric kinetic criterion can be used to select indeterminate simple waves and obtain the well-posedness of the local Riemann problem. A particular case is the entropic kinetic criterion of Hayes and Le Floch.

---

Sunto Principi di selezione cinetica sono stati mostrati utili e fisicamente ragionevoli in problemi iperbolici con transizioni di fase di grande ampiezza. Ci riferiamo ad Abeyaratne e Knowles, [A-K], per discussioni sull'argomento. Detti principi sono stati usati per problemi nonlineari degeneri, dove la proprietà di genuina nonlinearità di Lax è violata. Questo è la prospettiva di Liu, [Li], nella situazione cinetica di Hayes e Le Floch, [H-L], dove i loro così detti urti non classici possono essere considerati come transizioni di fase di piccola ampiezza. Qui, descriviamo la geometria locale generata dall'ipotesi generica genuinamente nonlineare. Un criterio di geometria cinetica può essere usato per selezionare onde semplici indeterminate ed ottenere la buona posizione per il problema locale di Riemann. Un caso particolare è il criterio di entropia cinetico di Hayes e Le Floc.