Approximation algorithms for the single-machine scheduling with a period of maintenance

We consider a single machine scheduling problem of minimizing total completion time subject to a period of maintenance, and design an \(O(nlogn)\) time algorithm with a tight performance ratio of \(17/15\). Then, we study an integrated production and distribution problem, in which jobs are delivered by one vehicle to a customer after they are completed on a single machine with a period of maintenance. The objective is to minimize total delivery time of the jobs. We develop a \(3/2\)-approximation algorithm with \(O(n^{3})\) time complexity.     

New complexity analysis of a full-Newton step feasible interior-point algorithm for $$P_*(\kappa )$$-LCP

In this paper, we consider a full-Newton step feasible interior-point algorithm for \(P_*(\kappa )\)-linear complementarity problem. The perturbed complementarity equation \(xs=\mu e\) is transformed by using a strictly increasing function, i.e., replacing \(xs=\mu e\) by \(\psi (xs)=\psi (\mu e)\) with \(\psi (t)=\sqrt{t}\), and the proposed interior-point algorithm is based on that algebraic equivalent transformation. Furthermore, we establish the currently best known iteration bound for \(P_*(\kappa )\)-linear complementarity problem, namely, \(O((1+4\kappa )\sqrt{n}\log \frac{n}{\varepsilon })\), which almost coincides with the bound derived for linear optimization, except that the iteration bound in the \(P_{*}(\kappa )\)-linear complementarity problem case is multiplied with the factor \((1+4\kappa )\).     

Polynomial convergence of two higher order interior-point methods for $$P_*(\kappa )$$-LCP in a wide neighborhood of the central path

In this paper, we propose two interior-point methods for solving \(P_*(\kappa )\)-linear complementarity problems (\(P_*(\kappa )\)-LCPs): a high order large update path following method and a high order corrector–predictor method. Both algorithms generate sequences of iterates in the wide neighborhood \((\mathcal {N}_{2,\tau }^-(\alpha ))\) of the central path introduced by Ai and Zhang. The methods do not depend on the handicap \(\kappa \) of the problem so that they work for any \(P_*(\kappa )\)-LCP . They have \(O((1 +\kappa )\sqrt{n}L)\) iteration complexity, the best-known iteration complexity obtained so far by any interior-point method for solving \(P_*(\kappa )\)-LCP. The high order corrector–predictor algorithm is superlinearly convergent with Q-order \((m_p+1)\) for problems that admit a strict complementarity solution and \((m_p+1)/2\) for general problems, where \(m_p\) is the order of the predictor step.     

An $$O(\sqrt{n}L)$$ iteration Mehrotra-type predictor-corrector algorithm for monotone linear complementarity problem

In this paper we propose a new class of Mehrotra-type predictor-corrector algorithm for the monotone linear complementarity problems (LCPs). At each iteration, the method computes a corrector direction in addition to the Ai–Zhang direction (SIAM J Optim 16:400–417, 2005), in an attempt to improve performance. Starting with a feasible point \((x^0, s^0)\) in the wide neighborhood \(\mathcal {N}(\tau ,\beta )\), the algorithm enjoys the low iteration bound of \(O(\sqrt{n}L)\), where \(n\) is the dimension of the problem and \(L=\log \frac{(x^0)^T s^0}{\varepsilon }\) with \(\varepsilon \) the required precision. We also prove that the new algorithm can be specified into an easy implementable variant for solving the monotone LCPs, in such a way that the iteration bound is still \(O(\sqrt{n}L)\). Some preliminary numerical results are provided as well.     

Uniform parallel machine scheduling problems with fixed machine cost

This paper considers two uniform parallel machine scheduling problems with fixed machine cost under the background of cloud manufacturing. The goal is to minimize the makespan with a given budget of total cost, \(\hat{U}\). All the jobs are homogeneous, i.e., the processing times of the jobs are identical. Non-preemptive and preemptive problems are studied. For the non-preemptive problem, we give a \(2[1+1{/}(h-1)]\)-approximation algorithm, where h is the number of the machine which can not be selected the first time. For the preemptive problem, we give an algorithm whose worst-case bound equals to \(1+1{/}(h-1)\). Preliminary experimental results indicate that the proposed algorithms are reasonably accurate compared with the lower bounds.     

Coalescece ad Meetig Times o $$$$-Block Markov Chais

We consider finite-state, discrete-time, mixing Markov chains \((V,P)\), where \(V\) is the state space and \(P\) is the transition matrix. To each such chain \((V,P)\), we associate a sequence of chains \((V_n,P_n)\) by coding trajectories of \((V,P)\) according to their overlapping \(n\)-blocks. The chain \((V_n,P_n)\), called the \(n\)-block Markov chain associated with \((V,P)\), may be considered an alternate version of \((V,P)\) having memory of length \(n\). Along such a sequence of chains, we characterize the asymptotic behavior of coalescence times and meeting times as \(n\) tends to infinity. In particular, we define an algebraic quantity \(L(V,P)\) depending only on \((V,P)\), and we show that if the coalescence time on \((V_n,P_n)\) is denoted by \(C_n\), then the quantity \(\frac{1}{n} \log C_n\) converges in probability to \(L(V,P)\) with exponential rate. Furthermore, we fully characterize the relationship between \(L(V,P)\) and the entropy of \((V,P)\).     

New computational guarantees for solving convex optimization problems with first order methods,via a function growth condition measure

Motivated by recent work of Renegar (A framework for applying subgradient methods to conic optimization problems, arXiv:1503.02611v2, 2015) we present new computational methods and associated computational guarantees for solving convex optimization problems using first-order methods. Our problem of interest is the general convex optimization problem \(f^* = \min _{x \in Q} f(x)\), where we presume knowledge of a strict lower bound \(f_{\mathrm{slb}}< f^*\). [Indeed, \(f_{\mathrm{slb}}\) is naturally known when optimizing many loss functions in statistics and machine learning (least-squares, logistic loss, exponential loss, total variation loss, etc.) as well as in Renegar’s transformed version of the standard conic optimization problem arXiv:1503.02611v2, 2015; in all these cases one has \(f_{\mathrm{slb}}= 0 < f^*\).] We introduce a new functional measure called the growth constant G for \(f(\cdot )\), that measures how quickly the level sets of \(f(\cdot )\) grow relative to the function value, and that plays a fundamental role in the complexity analysis. When \(f(\cdot )\) is non-smooth, we present new computational guarantees for the Subgradient Descent Method and for smoothing methods, that can improve existing computational guarantees in several ways, most notably when the initial iterate \(x^0\) is far from the optimal solution set. When \(f(\cdot )\) is smooth, we present a scheme for periodically restarting the Accelerated Gradient Method that can also improve existing computational guarantees when \(x^0\) is far from the optimal solution set, and in the presence of added structure we present a scheme using parametrically increased smoothing that further improves the associated computational guarantees.     

Regularity for Inhomogeneous Dirichlet Problems of Some Schrödinger Equations on Domains

Let \(n\ge 3, \Omega \) be a bounded, simply connected and semiconvex domain in \({\mathbb {R}}^n\) and \(L_{\Omega }:=-\Delta +V\) a Schrödinger operator on \(L^2 (\Omega )\) with the Dirichlet boundary condition, where \(\Delta \) denotes the Laplace operator and the potential \(0\le V\) belongs to the reverse Hölder class \(RH_{q_0}({\mathbb {R}}^n)\) for some \(q_0\in (\max \{n/2,2\},\infty ]\). Assume that the growth function \(\varphi :\,{\mathbb {R}}^n\times [0,\infty ) \rightarrow [0,\infty )\) satisfies that \(\varphi (x,\cdot )\) is an Orlicz function and \(\varphi (\cdot ,t)\in {\mathbb {A}}_{\infty }({\mathbb {R}}^n)\) (the class of uniformly Muckenhoupt weights). Let \(H_{\varphi ,\,L_{{\mathbb {R}}^n},\,r}(\Omega )\) be the Musielak–Orlicz–Hardy space whose elements are restrictions of elements of the Musielak–Orlicz–Hardy space, associated with \(L_{{\mathbb {R}}^n}:=-\Delta +V\) on \({\mathbb {R}}^n\), to \(\Omega \). In this article, the authors show that the operators \(VL^{-1}_\Omega \) and \(\nabla ^2L^{-1}_\Omega \) are bounded from \(L^1(\Omega )\) to weak-\(L^1(\Omega )\), from \(L^p(\Omega )\) to itself, with \(p\in (1,2]\), and also from \(H_{\varphi ,\,L_{{\mathbb {R}}^n},\,r}(\Omega )\) to the Musielak–Orlicz space \(L^\varphi (\Omega )\) or to \(H_{\varphi ,\,L_{{\mathbb {R}}^n},\,r}(\Omega )\) itself. As applications, the boundedness of \(\nabla ^2{\mathbb {G}}_D\) on \(L^p(\Omega )\), with \(p\in (1,2]\), and from \(H_{\varphi ,\,L_{{\mathbb {R}}^n},\,r}(\Omega )\) to \(L^\varphi (\Omega )\) or to \(H_{\varphi ,\,L_{{\mathbb {R}}^n},\,r}(\Omega )\) itself is obtained, where \({\mathbb {G}}_D\) denotes the Dirichlet Green operator associated with \(L_\Omega \). All these results are new even for the Hardy space \(H^1_{L_{{\mathbb {R}}^n},\,r}(\Omega )\), which is just \(H_{\varphi ,\,L_{{\mathbb {R}}^n},\,r}(\Omega )\) with \(\varphi (x,t):=t\) for all \(x\in {\mathbb {R}}^n\) and \(t\in [0,\infty )\).     

A $$$$ WP-Bailey lattice and its applications

In this paper, we establish a \(U(n+1)\) WP-Bailey lattice. By iterating this method, we obtain a \(U(n+1)\) transformation formula for \(U(n+1)\) WP-Bailey pairs. By considering the \(U(n+1)\) unit WP-Bailey pair, several new \(U(n+1)\) transformation formulas are given. In particular, we give a new \(U(n+1)\) Andrews–Gordon identity.     

Endotrivial modules for the general linear group in a nondefining characteristic

Suppose that \(G\) is a finite group such that \(\mathrm{SL }(n,q)\subseteq G \subseteq \mathrm{GL }(n,q)\), and that \(Z\) is a central subgroup of \(G\). Let \(T(G/Z)\) be the abelian group of equivalence classes of endotrivial \(k(G/Z)\)-modules, where \(k\) is an algebraically closed field of characteristic \(p\) not dividing \(q\). We show that the torsion free rank of \(T(G/Z)\) is at most one, and we determine \(T(G/Z)\) in the case that the Sylow \(p\)-subgroup of \(G\) is abelian and nontrivial. The proofs for the torsion subgroup of \(T(G/Z)\) use the theory of Young modules for \(\mathrm{GL }(n,q)\) and a new method due to Balmer for computing the kernel of restrictions in the group of endotrivial modules.     

Commuting traces of upper triangular matrix rings

Let \(T_n(R)\) be the upper triangular matrix ring over a unital ring R. Suppose that \(B:T_n(R)\times T_n(R) \rightarrow T_n(R)\) is a biadditive map such that \(B(X,X)X = XB(X,X)\) for all \(X \in T_n(R)\). We consider the problem of describing the form of the map \(X\mapsto B(X,X)\).     

An iterative algorithm for parametrization of shortest length linear shift registers over finite chain rings

The construction of shortest feedback shift registers for a finite sequence \(S_1,\ldots ,S_N\) is considered over finite chain rings, such as \({\mathbb Z}_{p^r}\). A novel algorithm is presented that yields a parametrization of all shortest feedback shift registers for the sequence of numbers \(S_1,\ldots ,S_N\), thus solving an open problem in the literature. The algorithm iteratively processes each number, starting with \(S_1\), and constructs at each step a particular type of minimal basis. The construction involves a simple update rule at each step which leads to computational efficiency. It is shown that the algorithm simultaneously computes a similar parametrization for the reverse sequence \(S_N,\ldots ,S_1\). The complexity order of the algorithm is shown to be \(O(r N^2)\).     

Some new Kirkman signal sets

A decomposition of the blocks of an \(\textsf {STS}(v)\) into partial parallel classes of size m is equivalent to a Kirkman signal set \(\textsf {KSS}(v,m)\). We give decompositions of \(\textsf {STS}(4v-3)\) into classes of size \(v-1\) when \(v \equiv 3 \pmod {6}\), \(v \not = 3\). We also give decompositions of \(\textsf {STS}(v)\) into classes of various sizes when v is a product of two arbitrary integers that are both congruent to \(3 \pmod {6}\). These results produce new families of \(\textsf {KSS}(v,m)\).     

Popular edges and dominant matchings

Given a bipartite graph \(G = (A \cup B,E)\) with strict preference lists and given an edge \(e^* \in E\), we ask if there exists a popular matching in G that contains \(e^*\). We call this the popular edge problem. A matching M is popular if there is no matching \(M'\) such that the vertices that prefer \(M'\) to M outnumber those that prefer M to \(M'\). It is known that every stable matching is popular; however G may have no stable matching with the edge \(e^*\). In this paper we identify another natural subclass of popular matchings called “dominant matchings” and show that if there is a popular matching that contains the edge \(e^*\), then there is either a stable matching that contains \(e^*\) or a dominant matching that contains \(e^*\). This allows us to design a linear time algorithm for identifying the set of popular edges. When preference lists are complete, we show an \(O(n^3)\) algorithm to find a popular matching containing a given set of edges or report that none exists, where \(n = |A| + |B|\).     

Extremal Problems for Mappings with Generalized Parametric Representation in $${{\mathbb {C}}}^{n}$$

In this paper we are concerned with the family \(\widetilde{S}^t_A(\mathbb {B}^n)\) (\(t\ge 0\)) of normalized biholomorphic mappings on the Euclidean unit ball \(\mathbb {B}^n\) in \({\mathbb {C}}^n\) that can be embedded in normal Loewner chains whose normalizations are given by time-dependent operators \(A\in \widetilde{\mathcal {A}}\), where \(\widetilde{\mathcal {A}}\) is a family of measurable mappings from \([0,\infty )\) into \(L({\mathbb {C}}^n)\) which satisfy certain natural assumptions. In particular, we consider extreme points and support points associated with the compact family \(\widetilde{S}^t_A(\mathbb {B}^n)\), where \(A\in \widetilde{\mathcal {A}}\). We prove that if \(f(z,t)=V(t)^{-1}z+\cdots \) is a normal Loewner chain such that \(V(s)f(\cdot ,s)\in \mathrm{ex}\,\widetilde{S}^s_A(\mathbb {B}^n)\) (resp. \(V(s)f(\cdot ,s)\in \mathrm{supp}\,\widetilde{S}^s_A(\mathbb {B}^n)\)), then \(V(t)f(\cdot ,t)\in \mathrm{ex}\, \widetilde{S}^t_A(\mathbb {B}^n)\), for all \(t\ge s\) (resp. \(V(t)f(\cdot ,t)\in \mathrm{supp}\,\widetilde{S}^t_A(\mathbb {B}^n)\), for all \(t\ge s\)), where V(t) is the unique solution on \([0,\infty )\) of the initial value problem: \(\frac{d V}{d t}(t)=-A(t)V(t)\), a.e. \(t\ge 0\), \(V(0)=I_n\). Also, we obtain an example of a bounded support point for the family \(\widetilde{S}_A^t(\mathbb {B}^2)\), where \(A\in \widetilde{\mathcal {A}}\) is a certain time-dependent operator. We also consider the notion of a reachable family with respect to time-dependent linear operators \(A\in \widetilde{\mathcal {A}}\), and obtain characterizations of extreme/support points associated with these families of bounded biholomorphic mappings on \(\mathbb {B}^n\). Useful examples and applications yield that the study of the family \(\widetilde{S}^t_A(\mathbb {B}^n)\) for time-dependent operators \(A\in \widetilde{\mathcal {A}}\) is basically different from that in the case of constant time-dependent linear operators.     

Improved upper bounds for partial spreads

A partial \((k-1)\)-spread in \({\text {PG}}(n-1,q)\) is a collection of \((k-1)\)-dimensional subspaces with trivial intersection. So far, the maximum size of a partial \((k-1)\)-spread in \({\text {PG}}(n-1,q)\) was known for the cases \(n\equiv 0\pmod k\), \(n\equiv 1\pmod k\), and \(n\equiv 2\pmod k\) with the additional requirements \(q=2\) and \(k=3\). We completely resolve the case \(n\equiv 2\pmod k\) for the binary case \(q=2\).     

On the finite basis problem for the monoids of partial extensive injective transformations

Let \(PEI_n (POEI_n)\) be the monoid of all partial (order-preserving) extensive and injective transformations over a chain of order n. We give a sufficient condition under which a semigroup is nonfinitely based and apply this condition to show that the monoid \(PEI_3 (POEI_3)\) is nonfinitely based. This together with the results of Edmunds and Goldberg gives a complete answer to the finite basis problem for the monoid \(PEI_n (POEI_n)\): the monoid \(PEI_n (POEI_n)\) is nonfinitely based if and only if \(n\geqslant 3\). Furthermore, it is shown that the monoid \(PEI_n (POEI_n)\) is hereditarily finitely based if and only if \(n\leqslant 2\).     

Fast approximation of matroid packing and covering

We study packing problems with matroid structures, which includes the strength of a graph of Cunningham and scheduling problems. If \(\mathcal {M}\) is a matroid over a set of elements S with independent set \(\mathcal {I}\), and \(m=|S|\), we suppose that we are given an oracle function that takes an independent set \(A\in \mathcal {I}\) and an element \(e\in S\) and determines if \(A\cup \{e\}\) is independent in time I(m). Also, given that the elements of A are represented in an ordered way \(A=\{A_1,\dots ,A_k\}\), we denote the time to check if \(A\cup \{e\}\notin \mathcal {I}\) and if so, to find the minimum \(i\in \{0,\dots ,k\}\) such that \(\{A_1,\dots ,A_i\}\cup \{e\}\notin \mathcal {I}\) by \(I^*(m)\). Then, we describe a new FPTAS that computes for any \(\varepsilon >0\) and for any matroid \(\mathcal {M}\) of rank r over a set S of m elements, in memory space O(m), the packing \(\varLambda ({\mathcal {M}})\) within \(1+\varepsilon \) in time \(O(mI^*(m)\log (m)\log (m/r)/\varepsilon ^2)\), and the covering \(\varUpsilon ({\mathcal {M}})\) in time \(O(r\varUpsilon ({\mathcal {M}})I(m)\log (m)\log (m/r)/\varepsilon ^2)\). This method outperforms in time complexity by a factor of \(\varOmega (m/r)\) the FPTAS of Plotkin, Shmoys, and Tardos, and a factor of \(\varOmega (m)\) the FPTAS of Garg and Konemann. On top of the value of the packing and the covering, our algorithm exhibits a combinatorial object that proves the approximation. The applications of this result include graph partitioning, minimum cuts, VLSI computing, job scheduling and others.