Nehari's problem and competing species systems

We consider an optimal partition problem in N-dimensional domains related to a method introduced by Nehari [22]. We prove existence of the minimal partition and some extremality conditions. Moreover we show some connections between the variational problem, the behaviour of competing species systems with large interaction and changing sign solutions to elliptic superlinear equations.     

A Variant of Multi-task n-vehicle Exploration Problem: Maximizing Every Processor’s Average Profit

We discuss a variant of the multi-task n-vehicle exploration problem. Instead of requiring an optimal permutation of vehicles in every group, the new problem requires all vehicles in a group to arrive at the same destination. Given n tasks with assigned consume-time and profit, it may also be viewed as a maximization of every processor’s average profit. Further, we propose a new kind of partition problem in fractional form and analyze its computational complexity. By regarding fractional partition as a special case, we prove that the average profit maximization problem is NP-hard when the number of processors is fixed and it is strongly NP- hard in general. At last, a pseudo-polynomial time algorithm for the average profit maximization problem and the fractional partition problem is presented, using the idea of the pseudo-polynomial time algorithm for the classical partition problem.     

The external constraint 4 nonempty part sandwich problem

List partitions generalize list colourings. Sandwich problems generalize recognition problems. The polynomial dichotomy (NP-complete versus polynomial) of list partition problems is solved for 4-dimensional partitions with the exception of one problem (the list stubborn problem) for which the complexity is known to be quasipolynomial. Every partition problem for 4 nonempty parts and only external constraints is known to be polynomial with the exception of one problem (the 2K₂-partition problem) for which the complexity of the corresponding list problem is known to be NP-complete. The present paper considers external constraint 4 nonempty part sandwich problems. We extend the tools developed for polynomial solutions of recognition problems obtaining polynomial solutions for most corresponding sandwich versions. We extend the tools developed for NP-complete reductions of sandwich partition problems obtaining the classification into NP-complete for some external constraint 4 nonempty part sandwich problems. On the other hand and additionally, we propose a general strategy for defining polynomial reductions from the 2K₂-partition problem to several external constraint 4 nonempty part sandwich problems, defining a class of 2K₂-hard problems. Finally, we discuss the complexity of the Skew Partition Sandwich Problem.     

Trace estimates for stable processes

In this paper we study the behaviour in time of the trace (the partition function) of the heat semigroup associated with symmetric stable processes in domains of R ^d . In particular, we show that for domains with the so called R-smoothness property the second terms in the asymptotic as t → 0 involves the surface area of the domain, just as in the case of Brownian motion.     

Optimal partitions

Consider a set of numbersZ={z ₁≥z ₂≥...≥z _n} and a functionf defined on subsets ofZ. LetP be a partition ofZ into disjoint subsetsS _i, say,g of them. The cost ofP is defined as $$C(P) = \sum\limits_{i = 1}^g {f(S_i )} .$$ By definition, in anordered partition, every pair of subsets has the property that the numbers in one subset are all greater than or equal to every number in the other subset. The problem of minimizingC(P) over all ordered partitions is called the optimal ordered partition problem. While no efficient method is known for solving the general optimal partition problem, the optimal ordered partition problem can be solved in quadratic time by dynamic programming. In this paper, we study the conditions onf under which an optimal ordered partition is indeed an optimal partition. In particular, we present an additive model and a multiplicative model for the functionf and give conditions such that the optimal partition problem can be reduced to the optimal ordered partition problem. We illustrate our results by applying them on problems which have been investigated previously in the literature.     

Constructing three-dimensional mappings onto the unit sphere with the hypercomplex Szegö kernel

In classical complex analysis the Szegö kernel method provides an explicit way to construct conformal maps from a given simply-connected domain G⊂C onto the unit disc. In this paper we revisit this method in the three-dimensional case. We investigate whether it is possible to construct three-dimensional mappings from some elementary domains into the three-dimensional unit ball by using the hypercomplex Szegö kernel. In the cases of rectangular domains, L-shaped domains, cylinders and the symmetric double-cone the proposed method leads surprisingly to qualitatively very good results. In the case of the cylinder we get even better results than those obtained by the hypercomplex Bergman method that was very recently proposed by several authors.We round off with also giving an explicit example of a domain, namely the T-piece, where the method does not lead to the desired result. This shows that one has to adapt the methods in accordance with different classes of domains.     

Scalar multidimensional conservation laws IBVP in noncylindrical Lipschitz domains

We study the initial-boundary-value problems for multidimensional scalar conservation laws in noncylindrical domains with Lipschitz boundary. We show the existence-uniqueness of this problem for initial-boundary data in L^∞ and the flux-function in the class C¹. In fact, first considering smooth boundary, we obtain the L¹-contraction property, discuss the existence problem and prove it by the Young measures theory. In the end we show how to pass the existence-uniqueness results on to some domains with Lipschitz boundary.     

Planar lattice gases with nearest-neighbor exclusion

We discuss the hard-hexagon and hard-square problems, as well as the corresponding problem on the honeycomb lattice. The case when the activity is unity is of interest to combinatorialists, being the problem of counting binary matrices with no two adjacent 1's. For this case, we use the powerful corner transfer matrix method to numerically evaluate the partition function per site, density and some near-neighbor correlations to high accuracy. In particular, for the square lattice, we obtain the partition function per site to 43 decimal places.     

Solving the segmentation problem for the 2010 Argentine census with integer programming

One of the most challenging tasks within the planning of a demographic census is to partition each census track into sets of homes such that each census taker visits exactly one set from this partition. In this work we introduce the home segmentation problem, which consists in designing such a partition subject to specific constraints. We present an integer programming-based algorithm for this problem, and we report the application of this algorithm for the 2010 census in the main province in Argentina.     

Parabolic spline interpolation for functions with large gradient in the boundary layer

We consider the problem of Subbotin’s parabolic spline interpolation for functions with large gradient domains. In the case of the common piecewise uniform Shishkin’s mesh we obtain two-sided accuracy estimates for the class of functions with exponential boundary layer. The spline interpolation accuracy estimates are not uniform in a small parameter, while the error itself can grow unboundedly as the small parameter vanishes and the number N of nodes remains fixed. We include the results of some simulations.     

Consensus of partitions : a constructive approach

Given a profile (family) ?? of partitions of a set of objects or items X, we try to establish a consensus partition containing a maximum number of joined or separated pairs in X that are also joined or separated in the profile. To do so, we define a score function, S _?? associated to any partition on X. Consensus partitions for ?? are those maximizing this function. Therefore, these consensus partitions have the median property for the profile and the symmetric difference distance. This optimization problem can be solved, in certain cases, by integer linear programming. We define a polynomial heuristic which can be applied to partitions on a large set of items. In cases where an optimal solution can be computed, we show that the partitions built by this algorithm are very close to the optimum which is reached in practically all the cases, except for some sets of bipartitions.     

On the Dirichlet problem for the prescribed mean curvature equation over general domains

We study and solve the Dirichlet problem for graphs of prescribed mean curvature in Rn+1 over general domains Ω without requiring a mean convexity assumption. By using pieces of nodoids as barriers we first give sufficient conditions for the solvability in case of zero boundary values. Applying a result by Schulz and Williams we can then also solve the Dirichlet problem for boundary values satisfying a Lipschitz condition.     

Exploring the VCG mechanism in combinatorial auctions: The threshold revenue and the threshold-price rule

We explore interesting potential extensions of the Vickrey–Clarke–Groves (VCG) rule under the assumption of players with independent and private valuations and no budget constraints. First, we apply the VCG rule to a coalition of bidders in order to compute the second price of the coalition. Then, we introduce and formulate the problem of determining that partition of players into coalitions which maximize the auctioneer’s revenue in the case whereby such coalitions take part to a VCG auction each one as a single agent; in particular, we provide an integer linear formulation of this problem. We also generalize this issue by allowing players to simultaneously belong to distinct coalitions in the case that players’ valuation functions are separable. Finally, we propose some applications of these theoretical results. For instance, we exploit them to provide a class of new payment rules and to decide which bids should be defined as the highest losing ones in combinatorial auctions.     

An O(n) algorithm to find a near-optimum partition of a convex polygon

This paper presents a heuristic algorithm to partition an n-sided convex polygon into n ? 2 nonintersecting triangles. Based on some theorems in [T. C. Hu and M. T. Shing, to appear], we can give a general formula to find the maximum ratio between the cost of the heuristic partition and the cost of the optimum partition and prove that this ratio never exceeds 1.155. We also given an example to show that the bound is tight.     

A mathematical programming problem with singular mixed pointwise-integral constraints

We investigate an infinite dimensional optimization problem which constraints are singular integral-pointwise ones. We give some partial results of existence for a solution in some particular cases. However, the lack of compactness, even in L¹ prevents to conclude in the general case. We give an existence result for a weak solution (as a measure) that we are able to describe. The regularity of such a solution is still an open problem.     

Graphical algebras — a new approach to congruence lattices

In 1970, H. Werner considered the question of which sublattices of partition lattices are congruence lattices for an algebra on the underlying set of the partition lattices. He showed that a complete sublattice of a partition lattice is a congruence lattice if and only if it is closed under a new operation called graphical composition. We study the properties of this new operation, viewed as an operation on an abstract lattice. We obtain some necessary properties, and we also obtain some sufficient conditions for an operation on an abstract lattice L to be this operation on a congruence lattice isomorphic to L. We use this result to give a new proof of Grätzer and Schmidt’s result that any algebraic lattice occurs as a congruence lattice.     

On Aleksandrov-Fenchel Inequalities for <Emphasis Type="Italic">k</Emphasis>-Convex Domains

In this lecture notes, we will discuss the classical Aleksandrov-Fenchel inequalities for quermassintegrals on convex domains and pose the problem of how to extend the inequalities to non-convex domains. We will survey some recent progress on the problem, then report some of our joint work [9] in which we generalize the k-th stage of the inequalities to a class of (k + 1)-convex domains. Our proof, following the earlier work of Castillion [8] for k =  1 case of the inequalities, uses the method of optimal transport.     

The behavior of the principal eigenvalue of a mixed elliptic problem with respect to a parameter

In this paper we determine the exact asymptotic behavior of the principal eigenvalue of a mixed elliptic eigenvalue problem which depends on a positive parameter λ when λ→∞. We analyze the case in which the problem is considered in a smooth bounded domain Ω of RN, and also the case of planar domains which are smooth except for a finite number of corner points.     

Fluctuations of the free energy in the high temperature Hopfield model

We consider the Hopfield model of size N and with p∼tN patterns, in the whole high temperature (paramagnetic) region. Our result is that the partition function has log-normal fluctuations. It is obtained by extending to the present model the method of the interpolating Brownian motions used by Comets (Comm. Math. Phys. 166 (1995) 549–564) for the Sherrington–Kirkpatrick model. We view the load t of the memory as a dynamical parameter, making the partition function a nice stochastic process. Then we write some semi-martingale decomposition for the logarithm of the partition function, and we prove that all the terms in this decomposition converge. In particular, the martingale term converges to a Gaussian martingale.