Nonlinear Fourier transforms for the sine-Gordon equation in the quarter plane

Using the Unified Transform, also known as the Fokas method, the solution of the sine-Gordon equation in the quarter plane can be expressed in terms of the solution of a matrix Riemann–Hilbert problem whose definition involves four spectral functions $a,b,A,B$. The functions $a(k)$ and $b(k)$ are defined via a nonlinear Fourier transform of the initial data, whereas $A(k)$ and $B(k)$ are defined via a nonlinear Fourier transform of the boundary values. In this paper, we provide an extensive study of these nonlinear Fourier transforms and the associated eigenfunctions under weak regularity and decay assumptions on the initial and boundary values. The results can be used to determine the long-time asymptotics of the sine-Gordon quarter-plane solution via nonlinear steepest descent techniques.     

The generalized nonlinear initial–boundary Riemann problem for quasilinear hyperbolic systems of conservation laws

In this paper, we study the nonlinear initial–boundary Riemann problem and the generalized nonlinear initial–boundary Riemann problem for quasilinear hyperbolic systems of conservation laws with nonlinear boundary conditions on the domain $\{(t,x)|t⩾0,x⩾0\}$. Under the assumption that each positive eigenvalue is either linearly degenerate or genuinely nonlinear, we get the existence and uniqueness of the self-similar solution to the nonlinear initial–boundary Riemann problem and of the global piecewise $C^1$ solution containing only shocks and (or) contact discontinuities to the corresponding generalized nonlinear initial–boundary Riemann problem. It shows that the self-similar solution to the nonlinear initial–boundary Riemann problem possesses the global structural stability.     

Optimal location of controllers for the one-dimensional wave equation

In this paper, we consider the homogeneous one-dimensional wave equation defined on $(0,\pi )$. For every subset $\omega ?[0,\pi ]$ of positive measure, every $T\ge 2\pi$, and all initial data, there exists a unique control of minimal norm in $L^2(0,T;L^2(\omega ))$ steering the system exactly to zero. In this article we consider two optimal design problems. Let $L\in (0,1)$. The first problem is to determine the optimal shape and position of ω in order to minimize the norm of the control for given initial data, over all possible measurable subsets ω of $[0,\pi ]$ of Lebesgue measure Lπ. The second problem is to minimize the norm of the control operator, over all such subsets. Considering a relaxed version of these optimal design problems, we show and characterize the emergence of different phenomena for the first problem depending on the choice of the initial data: existence of optimal sets having a finite or an infinite number of connected components, or nonexistence of an optimal set (relaxation phenomenon). The second problem does not admit any optimal solution except for $L=1/2$. Moreover, we provide an interpretation of these problems in terms of a classical optimal control problem for an infinite number of controlled ordinary differential equations. This new interpretation permits in turn to study modal approximations of the two problems and leads to new numerical algorithms. Their efficiency will be exhibited by several experiments and simulations.     

New algorithms for convex cost tension problem with application to computer vision

Motivated by various applications to computer vision, we consider the convex cost tension problem, which is the dual of the convex cost flow problem. In this paper, we first propose a primal algorithm for computing an optimal solution of the problem. Our primal algorithm iteratively updates primal variables by solving associated minimum cut problems. We show that the time complexity of the primal algorithm is $O(K?T(n,m))$, where $K$ is the range of primal variables and $T(n,m)$ is the time needed to compute a minimum cut in a graph with $n$ nodes and $m$ edges. We then develop an improved version of the primal algorithm, called the primal–dual algorithm, by making good use of dual variables in addition to primal variables. Although its time complexity is the same as that of the primal algorithm, we can expect a better performance in practice. We finally consider an application to a computer vision problem called the panoramic image stitching.     

Orienteering for electioneering

In this paper, we introduce a combinatorial optimization problem that models the investment decision a political candidate faces when treating his or her opponents’ campaign plans as given. Our formulation accounts for both the time cost of traveling between districts and the time expended while campaigning within districts. We describe a polynomial-time algorithm that computes a $(2+?)$-approximation to the optimal solution of a discrete version of our problem by reducing the problem to another combinatorial optimization problem known as Orienteering.     

Generalization of the double reduction theory

In a recent work Sjöberg (2007, 2008) [1], [2] remarked that generalization of the double reduction theory to partial differential equations of higher dimensions is still an open problem. In this note we have attempted to provide this generalization to find invariant solution for a non linear system of $q$th order partial differential equations with $n$ independent and $m$ dependent variables provided that the non linear system of partial differential equations admits a nontrivial conserved form which has at least one associated symmetry in every reduction. In order to give an application of the procedure we apply it to the nonlinear (2+1) wave equation for arbitrary function $f\left(u\right)$ and $g\left(u\right)$.     

Online maximum k-coverage

We study an online model for the maximum $k$-vertex-coverage problem, in which, given a graph $G=(V,E)$ and an integer $k$, we seek a subset $A?V$ such that $\left|A\right|=k$ and the number of edges covered by $A$ is maximized. In our model, at each step $i$, a new vertex $v_i$ is released, and we have to decide whether we will keep it or discard it. At any time of the process, only $k$ vertices can be kept in memory; if at some point the current solution already contains $k$ vertices, any inclusion of a new vertex in the solution must entail the definite deletion of another vertex of the current solution (a vertex not kept when released is definitely deleted). We propose algorithms for several natural classes of graphs (mainly regular and bipartite), improving on an easy $\frac{1}{2}$-competitive ratio. We next settle a set version of the problem, called the maximum $k$-(set)-coverage problem. For this problem, we present an algorithm that improves upon former results for the same model for small and moderate values of $k$.     

Greedy approximation for the source location problem with vertex-connectivity requirements in undirected graphs

Let $G=(V,E)$ be a simple undirected graph with a set V of vertices and a set E of edges. Each vertex $v\in V$ has a demand $d(v)\in Z_{+}$, and a cost $c(v)\in R_{+}$, where $Z_{+}$ and $R_{+}$ denote the set of nonnegative integers and the set of nonnegative reals, respectively. The source location problem with vertex-connectivity requirements in a given graph G asks to find a set S of vertices minimizing ${\sum }_{v\in S}c(v)$ such that there are at least $d(v)$ pairwise vertex-disjoint paths from S to v for each vertex $v\in V?S$. It is known that the problem is not approximable within a ratio of $O(\ln {\sum }_{v\in V}d(v))$, unless NP has an $O(N^{\log \log N})$-time deterministic algorithm. Also, it is known that even if every vertex has a uniform cost and $d^1=4$ holds, then the problem is NP-hard, where $d^1=\max \{d(v)|v\in V\}$.In this paper, we consider the problem in the case where every vertex has uniform cost. We propose a simple greedy algorithm for providing a $\max \{d^1,2d^1?6\}$-approximate solution to the problem in $O(\min \{d^1,\sqrt{|V|}\}{d}^1{|V|}^2)$ time, while we also show that there exists an instance for which it provides no better than a $(d^1?1)$-approximate solution. Especially, in the case of $d^1?4$, we give a tight analysis to show that it achieves an approximation ratio of 3. We also show the APX-hardness of the problem even restricted to $d^1?4$.     

An exact approach for the Vertex Coloring Problem

Given an undirected graph $G=(V,E)$, the Vertex Coloring Problem (VCP) requires to assign a color to each vertex in such a way that colors on adjacent vertices are different and the number of colors used is minimized. In this paper, we present an exact algorithm for the solution of VCP based on the well-known Set Covering formulation of the problem. We propose a Branch-and-Price algorithm embedding an effective heuristic from the literature and some methods for the solution of the slave problem, as well as two alternative branching schemes. Computational experiments on instances from the literature show the effectiveness of the algorithm, which is able to solve, for the first time to proven optimality, five of the benchmark instances in the literature, and reduce the optimality gap of many others.     

Improved Cotlar's inequality in the context of local Tb theorems

In the context of local Tb theorems with $L^p$ testing conditions we prove an enhanced Cotlar's inequality. This is related to the problem of removing the so called buffer assumption of Hytönen–Nazarov, which is the final barrier for the full solution of S. Hofmann's problem. We also investigate the problem of extending the Hytönen–Nazarov result to non-homogeneous measures. We work not just with the Lebesgue measure but with measures μ in ${\mathbb{R}}^d$ satisfying $\mu (B(x,r))\le C{r}^n$, $n\in (0,d]$. The range of exponents in the Cotlar type inequality depend on n. Without assuming buffer we get the full range of exponents $p,q\in (1,2]$ for measures with $n\le 1$, and in general we get $p,q\in [2??(n),2]$, $?(n)>0$. Consequences for (non-homogeneous) local Tb theorems are discussed.     

Viscosity solutions of obstacle problems for fully nonlinear path-dependent PDEs

In this article, we adapt the definition of viscosity solutions to the obstacle problem for fully nonlinear path-dependent PDEs with data uniformly continuous in $(t,\omega )$, and generator Lipschitz continuous in $(y,z,\gamma )$. We prove that our definition of viscosity solutions is consistent with the classical solutions, and satisfy a stability result. We show that the value functional defined via the second order reflected backward stochastic differential equation is the unique viscosity solution of the variational inequalities.     

A remark on the Bismut–Ricci form on 2-step nilmanifolds

In this note, we observe that, on a 2-step nilpotent Lie group equipped with a left-invariant SKT structure, the $(1,1)$-part of the Bismut–Ricci form is seminegative definite. As an application, we give a simplified proof of the non-existence of invariant SKT static metrics on 2-step nilmanifolds and of the existence of a long-time solution to the pluriclosed flow in 2-step nilmanifolds.     

Lower bounds for the Hilbert number of polynomial systems

Let $H(m)$ denote the maximal number of limit cycles of polynomial systems of degree m. It is called the Hilbert number. The main part of Hilbert?s 16th problem posed in 1900 is to find its value. The problem is still open even for $m=2$. However, there have been many interesting results on the lower bound of it for $m?2$. In this paper, we give some new lower bounds of this number. The results obtained in this paper improve all existing results for all $m?7$ based on some known results for $m=3,4,5,6$. In particular, we obtain that $H(m)$ grows at least as rapidly as $\frac{1}{2\ln 2}{(m+2)}^2\ln (m+2)$ for all large m.     

Upper and lower solutions and quasilinearization for a class of second order singular nonlinear differential equations with nonlinear boundary conditions

We consider the differential equation $-(1/w)({\mathit{pu}}^{\prime }{)}^{\prime }=f(·,u)$, where $f$ is a nonlinear function, with nonlinear boundary conditions. Under appropriate assumptions on $p,w,f$ and the boundary conditions, the existence of solutions is established. If the problem has a lower solution and an upper solution, then we use a quasilinearization method to obtain two monotonic sequences of approximate solutions converging quadratically to a solution of the equation.