Speeding up branch and bound algorithms for solving the maximum clique problem

In this paper we consider two branch and bound algorithms for the maximum clique problem which demonstrate the best performance on DIMACS instances among the existing methods. These algorithms are MCS algorithm by Tomita et al. (2010) and MAXSAT algorithm by Li and Quan (2010a, b). We suggest a general approach which allows us to speed up considerably these branch and bound algorithms on hard instances. The idea is to apply a powerful heuristic for obtaining an initial solution of high quality. This solution is then used to prune branches in the main branch and bound algorithm. For this purpose we apply ILS heuristic by Andrade et al. (J Heuristics 18(4):525–547, 2012). The best results are obtained for p_hat1000-3 instance and gen instances with up to 11,000 times speedup.     

A symmetry property for q-weighted Robinson–Schensted and other branching insertion algorithms

In [19], a \(q\) -weighted version of the Robinson–Schensted algorithm was introduced. In this paper, we show that this algorithm has a symmetry property analogous to the well-known symmetry property of the usual Robinson–Schensted algorithm. The proof uses a generalisation of the growth diagram approach introduced by Fomin [5–8]. This approach, which uses ‘growth graphs’, can also be applied to a wider class of insertion algorithms which have a branching structure, including some of the other \(q\) -weighted versions of the Robinson–Schensted algorithm which have recently been introduced by Borodin–Petrov [2].     

The strong convergence of a three-step algorithm for the split feasibility problem

Based on the very recent work by Dang and Gao (Invers Probl 27:1–9, 2011) and Wang and Xu (J Inequal Appl, doi:10.1155/2010/102085, 2010), and inspired by Yao (Appl Math Comput 186:1551–1558, 2007), Noor (J Math Anal Appl 251:217–229, 2000), and Xu (Invers Probl 22:2021–2034, 2006), we suggest a three-step KM-CQ-like method for solving the split common fixed-point problems in Hilbert spaces. Our results improve and develop previously discussed feasibility problem and related algorithms.     

Computing Final Polynomials and Final Syzygies Using Buchberger’s Gröbner Bases Method

Final polynomials and final syzygies provide an explicit representation of polynomial identities promised by Hilbert’s Nullstellensatz. Such representations have been studied independently by Bokowski [2,3,4] and Whiteley [23,24] to derive invariant algebraic proofs for statements in geometry. In the present paper we relate these methods to some recent developments in computational algebraic geometry. As the main new result we give an algorithm based on B. Buchberger’s Gröbner bases method for computing final polynomials and final syzygies over the complex numbers. Degree upper bound for final polynomials are derived from theorems of Lazard and Brownawell, and a topological criterion is proved for the existence of final syzygies. The second part of this paper is expository and discusses applications of our algorithm to real projective geometry, invariant theory and matrix theory.     

A tableau formula for eta polynomials

We use the Pieri and Giambelli formulas of Buch et al. (Invent Math 178:345–405, 2009; J Reine Angew, 2013) and the calculus of raising operators developed in Buch et al. (A Giambelli formula for isotropic Grassmannians, arXiv:0811.2781, 2008) and Tamvakis (J Reine Angew Math 652, 207–244, 2011) to prove a tableau formula for the eta polynomials of Buch et al. (J Reine Angew, 2013) and the Stanley symmetric functions which correspond to Grassmannian elements of the Weyl group $\widetilde{W}_n$ of type $\text {D}_n$ . We define the skew elements of $\widetilde{W}_n$ and exhibit a bijection between the set of reduced words for any skew $w\in \widetilde{W}_n$ and a set of certain standard typed tableaux on a skew shape $\lambda /\mu $ associated to $w$ .     

Exponential polynomials on commutative hypergroups

Polynomials and exponential polynomials play a fundamental role in the theory of spectral analysis and spectral synthesis on commutative groups. Recently several new results have been published in this field [2–4,6]. Spectral analysis and spectral synthesis has been studied on some types of commutative hypergroups, as well. However, a satisfactory definition of exponential monomials on general commutative hypergroups has not been available so far. In [5,7,8] and [9], the authors use a special concept on polynomial and Sturm–Liouville-hypergroups. Here we give a general definition which covers the known special cases.     

Strong NP-hardness of scheduling problems with learning or aging effect

Proofs of strong NP-hardness of single machine and two-machine flowshop scheduling problems with learning or aging effect given in Rudek (Computers & Industrial Engineering 61:20–31, 2011; Annals of Operations Research 196(1):491–516, 2012a; International Journal of Advanced Manufacturing Technology 59:299–309, 2012b; Applied Mathematics and Computations 218:6498–6510, 2012c; Applied Mathematical Modelling 37:1523–1536, 2013) contain a common mistake that make them incomplete. We reveal the mistake and provide necessary corrections for the problems in Rudek (Computers & Industrial Engineering 61:20–31, 2011; Annals of Operations Research 196(1):491–516, 2012a; Applied Mathematical Modelling 37:1523–1536, 2013). NP-hardness of problems in Rudek (International Journal of Advanced Manufacturing Technology 59:299–309, 2012b; Applied Mathematics and Computations 218:6498–6510, 2012c) remains unknown because of another mistake which we are unable to correct.     

On Ulm’s method for Fréchet differentiable operators

We provide new sufficient convergence conditions for the semilocal convergence of Ulm’s method (Izv. Akad. Nauk Est. SSR 16:403–411, 1967) in order to approximate a locally unique solution of an equation in a Banach space setting. We show that in some cases, our hypotheses hold true but the corresponding ones (Burmeister in Z. Angew. Math. Mech. 52:101–110, 1972; Kornstaedt in Aequ. Math. 13:21–45, 1975; Petzeltova in Comment. Math. Univ. Carol. 21:719–725, 1980; Potra and Ptǎk in Cas. Pest. Mat. 108:333–341, 1983; Ulm in Izv. Akad. Nauk Est. SSR 16:403–411, 1967) do not. We also show that under the same hypotheses and computational cost as (Burmeister in Z. Angew. Math. Mech. 52:101–110, 1972; Kornstaedt in Aequ. Math. 13:21–45, 1975; Petzeltova in Comment. Math. Univ. Carol. 21:719–725, 1980; Potra and Ptǎk in Cas. Pest. Mat. 108:333–341, 1983; Ulm in Izv. Akad. Nauk Est. SSR 16:403–411, 1967) finer error sequences can be obtained. Numerical examples are also provided further validating the results.     

Semiclassics for Particles with Spin via a Wigner–Weyl-Type Calculus

We show how to relate the full quantum dynamics of a spin-½ particle on \({\mathbb{R}^d}\) to a classical Hamiltonian dynamics on the enlarged phase space \({\mathbb{R}^{2d} \times \mathbb{S}^{2}}\) up to errors of second order in the semiclassical parameter. This is done via an Egorov-type theorem for normal Wigner–Weyl calculus for \({\mathbb{R}^d}\) (Folland, Harmonic Analysis on Phase Space, 1989; Lein, Weyl Quantization and Semiclassics, 2010) combined with the Stratonovich–Weyl calculus for SU(2) (Varilly and Gracia-Bondia, Ann Phys 190:107–148, 1989). For a specific class of Hamiltonians, including the Rabi- and Jaynes–Cummings model, we prove an Egorov theorem for times much longer than the semiclassical time scale. We illustrate the approach for a simple model of the Stern–Gerlach experiment.     

L p -theory for second-order elliptic operators with unbounded coefficients

Second-order elliptic operators with unbounded coefficients of the form ${Au := -{\rm div}(a\nabla u) + F . \nabla u + Vu}$ in ${L^{p}(\mathbb{R}^{N}) (N \in \mathbb{N}, 1 < p < \infty)}$ are considered, which are the same as in recent papers Metafune et?al. (Z Anal Anwendungen 24:497–521, 2005), Arendt et?al. (J Operator Theory 55:185–211, 2006; J Math Anal Appl 338: 505–517, 2008) and Metafune et?al. (Forum Math 22:583–601, 2010). A new criterion for the m-accretivity and m-sectoriality of A in ${L^{p}(\mathbb{R}^{N})}$ is presented via a certain identity that behaves like a sesquilinear form over L ^p ×?L ^p'. It partially improves the results in (Metafune et?al. in Z Anal Anwendungen 24:497–521, 2005) and (Metafune et?al. in Forum Math 22:583–601, 2010) with a different approach. The result naturally extends Kato’s criterion in (Kato in Math Stud 55:253–266, 1981) for the nonnegative selfadjointness to the case of p ≠?2. The simplicity is illustrated with the typical example ${Au = -u\hspace{1pt}'' + x^{3}u\hspace{1pt}' + c |x|^{\gamma}u}$ in ${L^p(\mathbb{R})}$ which is dealt with in (Arendt et?al. in J Operator Theory 55:185–211, 2006; Arendt et?al. in J Math Anal Appl 338: 505–517, 2008).     

The Shapley value for shortest path games: a non-graph-based approach

The shortest path games are considered in this paper. The transportation of a good in a network has costs and benefits. The problem is to divide the profit of the transportation among the players. Fragnelli et al. (Math Methods Oper Res 52: 251–264, 2000) introduce the class of shortest path games and show it coincides with the class of monotone games. They also give a characterization of the Shapley value on this class of games. In this paper we consider further five characterizations of the Shapley value (Hart and Mas-Colell’s in Econometrica 57:589–614, 1989; Shapley’s in Contributions to the theory of games II, annals of mathematics studies, vol 28. Princeton University Press, Princeton, pp 307–317, 1953; Young’s in Int J Game Theory 14:65–72, 1985, Chun’s in Games Econ Behav 45:119–130, 1989; van den Brink’s in Int J Game Theory 30:309–319, 2001 axiomatizations), and conclude that all the mentioned axiomatizations are valid for the shortest path games. Fragnelli et al. (Math Methods Oper Res 52:251–264, 2000)’s axioms are based on the graph behind the problem, in this paper we do not consider graph specific axioms, we take $TU$ axioms only, that is we consider all shortest path problems and we take the viewpoint of an abstract decision maker who focuses rather on the abstract problem than on the concrete situations.     

Modularity and monotonicity of games

The purpose of this paper is twofold. First, we generalize Kajii et al. (J Math Econ 43:218–230, 2007) and provide a condition under which for a game \(v\) , its Möbius inverse is equal to zero within the framework of the \(k\) -modularity of \(v\) for \(k \ge 2\) . This condition is more general than that in Kajii et al. (J Math Econ 43:218–230, 2007). Second, we provide a condition under which for a game \(v\) , its Möbius inverse takes non-negative values, and not just zero. This paper relates the study of totally monotone games to that of \(k\) -monotone games. Furthermore, this paper shows that the modularity of a game is related to \(k\) -additive capacities proposed by Grabisch (Fuzzy Sets Syst 92:167–189, 1997). To illustrate its application in the field of economics, we use these results to characterize a Gini index representation of Ben-Porath and Gilboa (J Econ Theory 64:443–467, 1994). Our results can also be applied to potential functions proposed by Hart and Mas-Colell (Econometrica 57:589–614, 1989) and further analyzed by Ui et al. (Math Methods Oper Res 74:427–443, 2011).     

An improved local convergence analysis for a two-step Steffensen-type method

We study a class of Steffensen-type algorithm for solving nonsmooth variational inclusions in Banach spaces. We provide a local convergence analysis under ω-conditioned divided difference, and the Aubin continuity property. This work on the one hand extends the results on local convergence of Steffensen’s method related to the resolution of nonlinear equations (see Amat and Busquier in Comput. Math. Appl. 49:13–22, 2005; J. Math. Anal. Appl. 324:1084–1092, 2006; Argyros in Southwest J. Pure Appl. Math. 1:23–29, 1997; Nonlinear Anal. 62:179–194, 2005; J. Math. Anal. Appl. 322:146–157, 2006; Rev. Colomb. Math. 40:65–73, 2006; Computational Theory of Iterative Methods, 2007). On the other hand our approach improves the ratio of convergence and enlarges the convergence ball under weaker hypotheses than one given in Hilout (Commun. Appl. Nonlinear Anal. 14:27–34, 2007).     

On Constrained Markov–Nikolskii type Inequalities for k-Absolutely Monotone Polynomials

We consider a classical problem of estimating norms of higher order derivatives of an algebraic polynomial via the norms of the polynomial itself. The corresponding extremal problem for general polynomials in the uniform norm was solved by V. A. Markov. In 1926, Bernstein found the exact constant in the Markov inequality for monotone polynomials. It was shown in [3] that the order of the constants in constrained Markov–Nikolskii inequality for k-absolutely monotone polynomials is the same as in the classical one in case \({0 < p \leqq q \leqq \infty}\) . In this paper, we find the exact order for all values of \({0 < p, q \leqq \infty}\) . It turnes out that for the case q < p the constrained Markov–Nikolskii inequality is significantly better than the unconstrained one.     

Tilting Theory and Functor Categories I. Classical Tilting

Tilting theory has been a very important tool in the classification of finite dimensional algebras of finite and tame representation type, as well as, in many other branches of mathematics. Happel (1988) and Cline et al. (J Algebra 304:397–409 1986) proved that generalized tilting induces derived equivalences between module categories, and tilting complexes were used by Rickard (J Lond Math Soc 39:436–456, 1989) to develop a general Morita theory of derived categories. On the other hand, functor categories were introduced in representation theory by Auslander (I Commun Algebra 1(3):177–268, 1974), Auslander (1971) and used in his proof of the first Brauer–Thrall conjecture (Auslander 1978) and later on, used systematically in his joint work with I. Reiten on stable equivalence (Auslander and Reiten, Adv Math 12(3):306–366, 1974), Auslander and Reiten (1973) and many other applications. Recently, functor categories were used in Martínez-Villa and Solberg (J Algebra 323(5):1369–1407, 2010) to study the Auslander–Reiten components of finite dimensional algebras. The aim of this paper is to extend tilting theory to arbitrary functor categories, having in mind applications to the functor category Mod (mod_Λ), with Λ a finite dimensional algebra.     

When a vector quasimonotone mapping is a vector monotone mapping

In this paper we provide a sufficient conditions that under them a vector quasimonotone set-valued mapping transfer to a vector monotone set-valued mapping. In fact this note is a vector version of the papers (Farajzadeh, J Ineq Appl 2012:192, 2012) and (Hadjisavvas, Appl Math Lett 19:913–915, 2006).     

Implicit and explicit algorithms for solving the split feasibility problem

Very recently, Dang and Gao (Inverse Probl 27:015007, 2011) introduced a KM-CQ algorithm with strong convergence for the split feasibility problem. In this paper, we will continue to consider the split feasibility problem. We present two algorithms. First, we introduce an implicit algorithm. Consequently, by discretizing the continuous implicit algorithm, we obtain an explicit algorithm. Under some weaker conditions, we show the strong convergence of presented algorithms to some solution of the split feasibility problem which solves some special variational inequality. As special cases, we obtain two algorithms which converge strongly to the minimum norm solution of the split feasibility problem. Results obtained in this paper include the corresponding results of Dang and Gao (2011) and extend a recent result of Wang and Xu (J Inequalities Appl 2010, doi:10.1155/2010/102085).     

Nilpotent Gelfand pairs and spherical transforms of Schwartz functions I: rank-one actions on the centre

The spectrum of a Gelfand pair of the form ${(K\ltimes N,K)}$ , where N is a nilpotent group, can be embedded in a Euclidean space ${{\mathbb R}^d}$ . The identification of the spherical transforms of K-invariant Schwartz functions on N with the restrictions to the spectrum of Schwartz functions on ${{\mathbb R}^d}$ has been proved already when N is a Heisenberg group and in the case where N?=?N _3,2 is the free two-step nilpotent Lie group with three generators, with K?=?SO₃ (Astengo et?al. in J Funct Anal 251:772–791, 2007; Astengo et?al. in J Funct Anal 256:1565–1587, 2009; Fischer and Ricci in Ann Inst Fourier Gren 59:2143–2168, 2009). We prove that the same identification holds for all pairs in which the K-orbits in the centre of N are spheres. In the appendix, we produce bases of K-invariant polynomials on the Lie algebra ${{\mathfrak n}}$ of N for all Gelfand pairs ${(K\ltimes N,K)}$ in Vinberg’s list (Vinberg in Trans Moscow Math Soc 64:47–80, 2003; Yakimova in Transform Groups 11:305–335, 2006).