Exact L 2-norm plane separation

We consider the problem of separating two sets of points in an n-dimensional real space with a (hyper)plane that minimizes the sum of L _p -norm distances to the plane of points lying on the wrong side of it. Despite recent progress, practical techniques for the exact solution of cases other than the L ₁ and L _∞-norm were unavailable. We propose and implement a new approach, based on non-convex quadratic programming, for the exact solution of the L ₂-norm case. We solve in reasonable computing times artificial problems of up to 20000 points (in 6 dimensions) and 13 dimensions (with 2000 points). We also observe that, for difficult real-life instances from the UCI Repository, computation times are substantially reduced by incorporating heuristic results in the exact solution process. Finally, we compare the classification performance of the planes obtained for the L ₁, L ₂ and L _∞ formulations. It appears that, despite the fact that L ₂ formulation is computationally more expensive, it does not give significantly better results than the L ₁ and L _∞ formulations.     

A 3/4-Approximation Algorithm for Multiple Subset Sum

The Multiple Subset Sum Problem (MSSP) is the variant of bin packing in which the number of bins is given and one would like to maximize the overall weight of the items packed in the bins. The problem is also a special case of the multiple knapsack problem in which all knapsacks have the same capacity and the item profits and weights coincide. Recently, polynomial time approximation schemes have been proposed for MSSP and its generalizations, see A. Caprara, H. Kellerer, and U. Pferschy (SIAM J. on Optimization, Vol. 11, pp. 308–319, 2000; Information Processing Letters, Vol. 73, pp. 111–118, 2000), C. Chekuri and S. Khanna (Proceedings of SODA 00, 2000, pp. 213–222), and H. Kellerer (Proceedings of APPROX, 1999, pp. 51–62). However, these schemes are only of theoretical interest, since they require either the solution of huge integer linear programs, or the enumeration of a huge number of possible solutions, for any reasonable value of required accuracy. In this paper, we present a polynomial-time 3/4-approximation algorithm which runs fast also in practice. Its running time is linear in the number of items and quadratic in the number of bins. The core of the algorithm is a procedure to pack triples of large items into the bins. As a byproduct of our analysis, we get the approximation guarantee for a natural greedy heuristic for the 3-Partitioning Problem.     

Infinitesimally homogeneous submanifolds of euclidean spaces

For a class of submanifolds of ^N, the infinitesimally homogeneous ones, the second fundamental form and itss-times iterated derivativessk+1 at any fixed point determine the immersion uniquely. The integerk>0 will be called the extrinsic Singer invariant. Any infinitesimally homogeneous submanifoldM (which is not necessarily complete) is an open part of a globally homogeneous (complete) submanifold. Indeed, the infinitesimal data at any pointp, determine, canonically, a Lie subgroupG of the isometry group of ^N , whose orbit atp is a complete submanifold that extendsM. Work partially supported by the GNSAGA of CNR and by the MURST of Italy     

Nonadaptive search problem with sets of equal sum

Consider the set A={1,2,3,…,2 ⁿ }, n≥3 and let x∈ A be unknown element. For given natural number S we are allowed to ask whether x belongs to a subset B of A such that the sum of the elements of B equals S. We investigate for which S it is possible to find x using a nonadaptive search.     

A MIP approach for some practical packing problems: Balancing constraints and tetris-like items

This paper considers packing problems with balancing conditions and items consisting of clusters of parallelepipeds (mutually orthogonal, i.e. tetris-like items). This issue is quite frequent in space engineering and a real-world application deals with the Automated Transfer Vehicle project (funded by the European Space Agency), at present under development. A Mixed Integer Programming (MIP) approach is proposed. The three-dimensional single bin packing problem is considered. It consists of orthogonally placing, with possibility of rotation, the maximum number of parallelepipeds into a given parallelepiped. A MIP formulation of the problem is reported together with a MIP-based heuristic approach. Balancing conditions are furthermore examined, as well as the orthogonal placement (with rotation) of tetris-like items into a rectangular domain.Received: September 2003, Revised: February 2004, AMS classification: 90B99, 05B40, 90C90, 90C59Thanks are due to T. A. Ciriani for the important suggestions given for the whole paper and to S. Gliozzi (IBM, Business Consulting Services) for the significant support offered, in particular in discussing the topics presented in Sect. 2.1.     

(k,c) – coloring via Column Generation

In this paper we study the (k,c) – coloring problem, a generalization of the well known Vertex Coloring Problem (VCP). We propose a new formulation and compare it computationally with another formulation from the literature. We also develop a diving heuristic that provides with good quality results at a reasonable computational effort.     

Resource assignment with preference conditions

This paper deals with a modification of the standard assignment problem, where subsets of resources express preferences in being, or not being, assigned together to the same activity. The problem arises in several real settings, among which the job assignment of the crew personnel of an airline company. We provide an integer programming formulation for both the Split Preference Problem, where couples of assignees do not want to work together, and for the Join Preference Problem, where, oppositely, couples of assignees want to work together. The mathematical nature of the two problems is indeed different, as for the first one it is possible to determine a minimum cost flow formulation on a suitable graph, and thus a polynomial time algorithm, while for the second one we face a NP-hard problem and device some heuristic solution approaches. Experimental tests conducted on instances of variable size confirm the effectiveness of the models and of the algorithms proposed.     

A Cut and Branch Approach for the Capacitated <Emphasis Type="Italic">p</Emphasis>-Median Problem Based on Fenchel Cutting Planes

The capacitated p-median problem (CPMP) consists of finding p nodes (the median nodes) minimizing the total distance to the other nodes of the graph, with the constraint that the total demand of the nodes assigned to each median does not exceed its given capacity. In this paper we propose a cutting plane algorithm, based on Fenchel cuts, which allows us to considerably reduce the integrality gap of hard CPMP instances. The formulation strengthened with Fenchel cuts is solved by a commercial MIP solver. Computational results show that this approach is effective in solving hard instances or considerably reducing their integrality gap.      

Using scenario trees and progressive hedging for stochastic inventory routing problems

The Stochastic Inventory Routing Problem is a challenging problem, combining inventory management and vehicle routing, as well as including stochastic customer demands. The problem can be described by a discounted, infinite horizon Markov Decision Problem, but it has been showed that this can be effectively approximated by solving a finite scenario tree based problem at each epoch. In this paper the use of the Progressive Hedging Algorithm for solving these scenario tree based problems is examined. The Progressive Hedging Algorithm can be suitable for large-scale problems, by giving an effective decomposition, but is not trivially implemented for non-convex problems. Attempting to improve the solution process, the standard algorithm is extended with locking mechanisms, dynamic multiple penalty parameters, and heuristic intermediate solutions. Extensive computational results are reported, giving further insights into the use of scenario trees as approximations of Markov Decision Problem formulations of the Stochastic Inventory Routing Problem.     

A priori estimates of strong solutions of semilinear parabolic equations

We study an initial boundary value problem for the semilinear parabolic equation

Entrywise relative perturbation theory for nonsingularM-matrices and applications

This paper establishes a new entrywise relative perturbation result for the inverse of a nonsingularM-matrixA. It is shown that a version of Gaussian elimination with one step of iterative refinement solves the systemAx =b, whereb is nonnegative, with small entrywise relative error. IfA is tridiagonal, the Gaussian elimination alone suffices.     

On weak neighborhood systems and spaces

We introduce and study the concepts of weak neighborhood systems, weak neighborhood spaces, ω(ψ, ψ′)-continuity, ω-continuity and ω*-continuity on WNS’s. This work was supported by a grant from Research Institute for Basic Science at Kangwon National University.     

Extending analyticK-subanalytic functions

Letg:U→ℝ (U open in ℝⁿ) be an analytic and K-subanalytic (i. e. definable in ℝ _an ^K , whereK, the field of exponents, is any subfield ofℝ) function. Then the set of points, denoted Σ, whereg does not admit an analytic extension is K-subanalytic andg can be extended analytically to a neighbourhood of Ū\∑. Partially supported by the European RTN Network RAAG (contract no. HPRN-CT-00271)     

A New Construction of Central Relative (p a , p a , p a , 1)-Difference Sets

Semiregular relative difference sets (RDS) in a finite group E which avoid a central subgroup C are equivalent to orthogonal cocycles. For example, every abelian semiregular RDS must arise from a symmetric orthogonal cocycle, and vice versa. Here, we introduce a new construction for central (p ^a , p ^a , p ^a , 1)-RDS which derives from a novel type of orthogonal cocycle, an LP cocycle, defined in terms of a linearised permutation (LP) polynomial and multiplication in a finite presemifield. The construction yields many new non-abelian (p ^a , p ^a , p ^a , 1)-RDS. We show that the subset of the LP cocycles defined by the identity LP polynomial and multiplication in a commutative semifield determines the known abelian (p ^a , p ^a , p ^a , 1)-RDS, and give a second new construction using presemifields.We use this cohomological approach to identify equivalence classes of central (p ^a , p ^a , p ^a , 1)-RDS with elementary abelian C and E/C. We show that for p = 2, a 3 and p = 3, a 2, every central (p ^a , p ^a , p ^a , 1)-RDS is equivalent to one arising from an LP cocycle, and list them all by equivalence class. For p = 2, a = 4, we list the 32 distinct equivalence classes which arise from field multiplication. We prove that, for any p, there are at least a equivalence classes of central (p ^a , p ^a , p ^a , 1)-RDS, of which one is abelian and a – 1 are non-abelian.     

Root Decomposition of the Ternary Malcev Algebra <Emphasis Type="Italic">M</Emphasis><Subscript>8</Subscript>

A root decomposition is constructed of the simple eight-dimensional ternary Malcev algebra M ₈. In result, M ₈ is equipped with a structure of a Z ₃-graded ternary algebra.Original Russian Text Copyright © 2005 Pozhidaev A. P.The author was supported by the Russian Science Support Foundation and partially by the Russian Foundation for Basic Research (Grant 05-01-00230).__________Translated from Sibirskii Matematicheskii Zhurnal, Vol. 46, No. 4, pp. 901–906, July–August, 2005.     

Separation properties forMW-fractals

Corresponding to the irreducible 0–1 matrix (a _ij ) _n×n , take similitude contraction mappingsϕ _ij for eacha _ij =1, ina _ij =1, in R ^d with ratio 0<r _ij <1. There are unique nonempty compact setsF ₁,…,F _n satisfying for each1≤i≤n, F _i. We prove that open set condition holds if and only ifF _i is ans-set for some1≤i≤n, wheres is such that the spectral radius of matrix (r _ij ³ ) _{n x n} is 1. Partly supported by Natural Science Foundation of China, and partly by Natural Science Foundation of Hubei Province     

Results on <Emphasis Type="Italic">F</Emphasis>-continuous graphs

For any nontrivial connected graph F and any graph G, the F-degree of a vertex v in G is the number of copies of F in G containing v. G is called F-continuous if and only if the F-degrees of any two adjacent vertices in G differ by at most 1; G is F-regular if the F-degrees of all vertices in G are the same. This paper classifies all P ₄-continuous graphs with girth greater than 3. We show that for any nontrivial connected graph F other than the star K _1,k , k ⩾ 1, there exists a regular graph that is not F-continuous. If F is 2-connected, then there exists a regular F-continuous graph that is not F-regular.      

On the K shortest path trees problem

We address the problem of finding the K best path trees connecting a source node with any other non-source node in a directed network with arbitrary lengths. The main result in this paper is the proof that the kth shortest path tree is adjacent to at least one of the previous (k-1) shortest path trees. Consequently, we design an O(f(n,m,C_max)+Km) time and O(K+m) space algorithm to determine the K shortest path trees, in a directed network with n nodes, m arcs and maximum absolute length C_max, where O(f(n,m,C_max)) is the best time needed to solve the shortest simple paths connecting a source node with any other non-source node.     

Orthogonal factorizations of digraphs

Let G be a digraph with vertex set V(G) and arc set E(G) and let g = (g ⁻, g ⁺) and ƒ = (ƒ ⁻, ƒ ⁺) be pairs of positive integer-valued functions defined on V(G) such that g ⁻(x) ⩽ ƒ ⁻(x) and g ⁺(x) ⩽ ƒ ⁺(x) for each x ∈ V(G). A (g, ƒ)-factor of G is a spanning subdigraph H of G such that g ⁻(x) ⩽ id _H (x) ⩽ ƒ ⁻(x) and g ⁺(x) ⩽ od _H (x) ⩽ ƒ ⁺(x) for each x ∈ V(H); a (g, ƒ)-factorization of G is a partition of E(G) into arc-disjoint (g, ƒ)-factors. Let = {F ₁, F ₂,…, F _m} and H be a factorization and a subdigraph of G, respectively. is called k-orthogonal to H if each F _i , 1 ⩽ i ⩽ m, has exactly k arcs in common with H. In this paper it is proved that every (mg+m−1,mƒ−m+1)-digraph has a (g, f)-factorization k-orthogonal to any given subdigraph with km arcs if k ⩽ min{g ⁻(x), g ⁺(x)} for any x ∈ V(G) and that every (mg, mf)-digraph has a (g, f)-factorization orthogonal to any given directed m-star if 0 ⩽ g(x) ⩽ f(x) for any x ∈ V(G). The results in this paper are in some sense best possible.      

Limiting -subgradient characterizations of constrained best approximation

In this paper, we show that the strong conical hull intersection property (CHIP) completely characterizes the best approximation to any x in a Hilbert space X from the set

K:=C∩{xX:-g(x)S},