The Gold Partition Conjecture

We present the Gold Partition Conjecture which immediately implies the – Conjecture and tight upper bound for sorting. We prove the Gold Partition Conjecture for posets of width two, semiorders and posets containing at most elements. We prove that the fraction of partial orders on an -element set satisfying our conjecture converges to when approaches infinity. We discuss properties of a hypothetical counterexample.     

The Wide Partition Conjecture and the Atom Problem in Discrete Tomography

The Wide Partition Conjecture (WPC) was introduced by Chow and B. Taylor as an attempt to prove inductively Rotaʼs Basis Conjecture, and in the simplest case tries to characterize partitions whose Young diagram admits a “Latin” filling. Chow et al. [T. Chow, C. K. Fan, M. Goemans, and J. Vondrak. Wide partitions, latin tableaux, and rotaʼs basis conjecture. Adv. in Appl. Math., 31(2):334–358, 2003] showed how the WPC is related to problems such as edge-list coloring and multi commodity flow. As far as we know, the conjecture remains widely open.We show that the WPC can be formulated using the k-atom problem in Discrete Tomography [C. Dürr, F. Guíñez, and M. Matamala. Reconstructing 3-Colored Grids from Horizontal and Vertical Projections is NP-Hard: A Solution to the 2-Atom Problem in Discrete Tomography. SIAM J Discrete Math, 26(1):330, 2012.]. In this approach, the WPC states that the sequences arising from partitions admit disjoint realizations if and only if any combination of them can be realizable independently. This realizability condition is not sufficient in general. A stronger condition, the saturation condition, was used in [F. Guíñez, M. Matamala, and S. Thomassé. Realizing disjoint degree sequences of span at most two: A tractable discrete tomography problem. Discrete Appl.Math., 159(1):23–30, 2011] to solve instances were the realizability condition fails. We prove that in our case, the saturation condition is satisfied providing the realizability condition does. Moreover, we show that the saturation condition can be obtained from the Langrangean dual of a natural LP formulation of the k-atom problem.     

Basis- and partition identification for quadratic programming and linear complementarity problems

Optimal solutions of interior point algorithms for linear and quadratic programming and linear complementarity problems provide maximally complementary solutions. Maximally complementary solutions can be characterized by optimal partitions. On the other hand, the solutions provided by simplex–based pivot algorithms are given in terms of complementary bases. A basis identification algorithm is an algorithm which generates a complementary basis, starting from any complementary solution. A partition identification algorithm is an algorithm which generates a maximally complementary solution (and its corresponding partition), starting from any complementary solution. In linear programming such algorithms were respectively proposed by Megiddo in 1991 and Balinski and Tucker in 1969. In this paper we will present identification algorithms for quadratic programming and linear complementarity problems with sufficient matrices. The presented algorithms are based on the principal pivot transform and the orthogonality property of basis tableaus. Received April 9, 1996 / Revised version received April 27, 1998? Published online May 12, 1999     

The 0-1 Knapsack problem with a single continuous variable

Specifically we investigate the polyhedral structure of the knapsack problem with a single continuous variable, called the mixed 0-1 knapsack problem. First different classes of facet-defining inequalities are derived based on restriction and lifting. The order of lifting, particularly of the continuous variable, plays an important role. Secondly we show that the flow cover inequalities derived for the single node flow set, consisting of arc flows into and out of a single node with binary variable lower and upper bounds on each arc, can be obtained from valid inequalities for the mixed 0-1 knapsack problem. Thus the separation heuristic we derive for mixed knapsack sets can also be used to derive cuts for more general mixed 0-1 constraints. Initial computational results on a variety of problems are presented. Received May 22, 1997 / Revised version received December 22, 1997 Published online November 24, 1998     

A stochastic programming model using an endogenously determined worst case risk measure for dynamic asset allocation

We present a new approach to asset allocation with transaction costs. A multiperiod stochastic linear programming model is developed where the risk is based on the worst case payoff that is endogenously determined by the model that balances expected return and risk. Utilizing portfolio protection and dynamic hedging, an investment portfolio similar to an option-like payoff structure on the initial investment portfolio is characterized. The relative changes in the expected terminal wealth, worst case payoff, and risk aversion, are studied theoretically and illustrated using a numerical example. This model dominates a static mean-variance model when the optimal portfolios are evaluated by the Sharpe ratio. Received: August 15, 1999 / Accepted: October 1, 2000?Published online December 15, 2000     

The global linear convergence of an infeasible non-interior path-following algorithm for complementarity problems with uniform P-functions

We propose an infeasible non-interior path-following method for nonlinear complementarity problems with uniform P-functions. This method is based on the smoothing techniques introduced by Kanzow. A key to our analysis is the introduction of a new notion of neighborhood for the central path which is suitable for infeasible non-interior path-following methods. By restricting the iterates in the neighborhood of the central path, we provide a systematic procedure to update the smoothing parameter and establish the global linear convergence of this method. Some preliminary computational results are reported. Received: March 13, 1997 / Accepted: December 17, 1999?Published online February 23, 2000     

Error bounds for 2-regular mappings with Lipschitzian derivatives and their applications

We obtain local estimates of the distance to a set defined by equality constraints under assumptions which are weaker than those previously used in the literature. Specifically, we assume that the constraints mapping has a Lipschitzian derivative, and satisfies a certain 2-regularity condition at the point under consideration. This setting directly subsumes the classical regular case and the twice differentiable 2-regular case, for which error bounds are known, but it is significantly richer than either of these two cases. When applied to a certain equation-based reformulation of the nonlinear complementarity problem, our results yield an error bound under an assumption more general than b-regularity. The latter appears to be the weakest assumption under which a local error bound for complementarity problems was previously available. We also discuss an application of our results to the convergence rate analysis of the exterior penalty method for solving irregular problems. Received: February 2000 / Accepted: November 2000?Published online January 17, 2001     

Leading coefficients of Kazhdan–Lusztig polynomials and fully commutative elements

Let W be a Coxeter group of type . We show that the leading coefficient, μ(x,w), of the Kazhdan–Lusztig polynomial P _x,w is always equal to 0 or 1 if x is fully commutative (and w is arbitrary).     

Entropic proximal decomposition methods for convex programs and variational inequalities

We consider convex optimization and variational inequality problems with a given separable structure. We propose a new decomposition method for these problems which combines the recent logarithmic-quadratic proximal theory introduced by the authors with a decomposition method given by Chen-Teboulle for convex problems with particular structure. The resulting method allows to produce for the first time provably convergent decomposition schemes based on C ^∞ Lagrangians for solving convex structured problems. Under the only assumption that the primal-dual problems have nonempty solution sets, global convergence of the primal-dual sequences produced by the algorithm is established. Received: October 6, 1999 / Accepted: February 2001?Published online September 17, 2001     

Linear preselective policies for stochastic project scheduling

In the context of stochastic resource-constrained project scheduling we introduce a novel class of scheduling policies, the linear preselective policies. They combine the benefits of preselective policies and priority policies; two classes that are well known from both deterministic and stochastic scheduling. We study several properties of this new class of policies which indicate its usefulness for computational purposes. Based on a new representation of preselective policies as and/or precedence constraints we derive efficient algorithms for computing earliest job start times and state a necessary and sufficient dominance criterion for preselective policies.  A computational experiment based on 480 instances empirically validates the theoretical findings.     

Nonlinear 0–1 programming: II. Dominance relations and algorithms

A nonlinear 0–1 program can be restated as a multilinear 0–1 program, which in turn is known to be equivalent to a linear 0–1 program with generalized covering (g.c.) inequalities. In a companion paper [6] we have defined a family of linear inequalities that contains more compact (smaller cardinality) linearizations of a multilinear 0–1 program than the one based on the g.c. inequalities. In this paper we analyze the dominance relations between inequalities of the above family. In particular, we give a criterion that can be checked in linear time, for deciding whether a g.c. inequality can be strengthened by extending the cover from which it was derived. We then describe a class of algorithms based on these results and discuss our computational experience. We conclude that the g.c. inequalities can be strengthened most of the time to an extent that increases with problem density. In particular, the algorithm using the strengthening procedure outperforms the one using only g.c. inequalities whenever the number of nonlinear terms per constraint exceeds about 12–15, and the difference in their performance grows with the number of such terms. Research supported by the National Science Foundation under grant ECS 7902506 and by the Office of Naval Research under contract N00014-75-C-0621 NR 047-048.     

The Local Stark Conjecture at a Real Place

A refinement of the rank 1 Abelian Stark conjecture has been formulated by B.Gross. This conjecture predicts some -adic analytic nature of a modification of the Stark unit. The conjecture makes perfect sense even when is an Archimedean place. Here we consider the conjecture when is a real place, and interpret it in terms of 2-adic properties of special values of L-functions. We prove the conjecture for CM extensions; here the original Stark conjecture is uninteresting, but the refined conjecture is nontrivial. In more generality, we show that, under mild hypotheses, if the subgroup of the Galois group generated by complex conjugations has less than full rank, then the refined conjecture implies that the Stark unit should be a square. This phenomenon has been discovered by Dummit and Hayes in a particular type of situation. We show that it should hold in much greater generality.     

The mean value property for harmonic functions on graphs and trees

Following the Euclidean example, we introduce the strong and weak mean value property for finite variation measures on graphs. We completely characterize finite variation measures with bounded support on radial trees which have the strong mean value property. We show that for counting measures on bounded subsets of a tree with root o, the strong mean value property is equivalent to the invariance of the subset under the action of the stabilizer of o in the automorphism group. We finally characterize, using the discrete Laplacian, the finite variation measures on a generic graph which have the weak mean value property and we give a non-trivial example. Received: July 21, 2000; in final form: March 13, 2001?Published online: March 19, 2002     

The Threshold for the Erdos, Jacobson and Lehel Conjecture to Be True

Let σ（k, n） be the smallest even integer such that each n-term positive graphic sequence with term sum at least σ（k, n） can be realized by a graph containing a clique of k ＋ 1 vertices. Erdos et al. （Graph Theory, 1991, 439-449） conjectured that σ（k, n） = （k - 1）（2n- k） ＋ 2. Li et al. （Science in China, 1998, 510-520） proved that the conjecture is true for k 〉 5 and n ≥ （k2） ＋ 3, and raised the problem of determining the smallest integer N（k） such that the conjecture holds for n ≥ N（k）. They also determined the values of N（k） for 2 ≤ k ≤ 7, and proved that [5k-1/2] ≤ N（k） ≤ （k2） ＋ 3 for k ≥ 8. In this paper, we determine the exact values of σ（k, n） for n ≥ 2k＋3 and k ≥ 6. Therefore, the problem of determining σ（k, n） is completely solved. In addition, we prove as a corollary that N（k） -= [5k-1/2] for k ≥6.     

Generalized Continuous Posets and a New Cartesian Closed Category

With every subset selection for posets, there is associated a certain ideal completion . As shown by Erné, such completions help to extend classical results on domains and similar structures in the absence of the required joins. Some results about –predistributive or –precontinuous posets and –continuous functions are summarized and supplemented. In particular, several central results on function spaces in domain theory are extended to the setting of productive closed subset selections. The category FSBP, in which objects are finitely separated and upper bounded posets and arrows are continuous functions between them, is shown to be cartesian closed. This research is supported by the National Natural Science Foundation of China, 10471035.     

New Branch-and-Cut Algorithm for Bilevel Linear Programming

Linear mixed 0–1 integer programming problems may be reformulated as equivalent continuous bilevel linear programming (BLP) problems. We exploit these equivalences to transpose the concept of mixed 0–1 Gomory cuts to BLP. The first phase of our new algorithm generates Gomory-like cuts. The second phase consists of a branch-and-bound procedure to ensure finite termination with a global optimal solution. Different features of the algorithm, in particular, the cut selection and branching criteria are studied in details. We propose also a set of algorithmic tests and procedures to improve the method. Finally, we illustrate the performance through numerical experiments. Our algorithm outperforms pure branch-and-bound when tested on a series of randomly generated problems. Work of the authors was partially supported by FCAR, MITACS and NSERC grants.     

The abc-conjecture for Algebraic Numbers

The abe-conjecture for the ring of integers states that, for every ε 〉 0 and every triple of relatively prime nonzero integers （a, b, c） satisfying a ＋ b = c, we have max（｜a｜, ｜b｜, ｜c｜） 〈 rad（abc）^1＋ε with a finite number of exceptions. Here the radical rad（m） is the product of all distinct prime factors of m. In the present paper we propose an abe-conjecture for the field of all algebraic numbers. It is based on the definition of the radical （in Section 1） and of the height （in Section 2） of an algebraic number. From this abc-conjecture we deduce some versions of Fermat＇s last theorem for the field of all algebraic numbers, and we discuss from this point of view known results on solutions of Fermat＇s equation in fields of small degrees over Q.     

Λsp-sets and some weak separation axioms

We shall introduce the notions of Λsp-closed and spg-closed sets. We also investigate properties of these sets and introduce some related new separation axioms. This revised version was published online in June 2006 with corrections to the Cover Date.     

Testing optimality for quadratic 0-1 problems

Received June 4, 1996 / Revised version received November 19, 1997 Published online November 24, 1998