Exact algorithms for the Hamiltonian cycle problem in planar graphs

We construct an exact algorithm for the Hamiltonian cycle problem in planar graphs with worst case time complexity , where c is some fixed constant that does not depend on the instance. Furthermore, we show that under the exponential time hypothesis, the time complexity cannot be improved to .     

An approximation algorithm for maximum triangle packing

We present a randomized -approximation algorithm for the weighted maximum triangle packing problem, for any given ε>0. This is the first algorithm for this problem whose performance guarantee is better than . The algorithm also improves the best-known approximation bound for the maximum 2-edge path packing problem.     

An improved randomized approximation algorithm for maximum triangle packing

This paper deals with the maximum triangle packing problem. For this problem, Hassin and Rubinstein gave a randomized polynomial-time approximation algorithm that achieves an expected ratio of for any constant ?>0. By modifying their algorithm, we obtain a new randomized polynomial-time approximation algorithm for the problem which achieves an expected ratio of 0.5257(1−?) for any constant ?>0.     

On-line scheduling on a batch machine to minimize makespan with limited restarts

We study the on-line scheduling on an unbounded batch machine to minimize makespan. In this model, jobs arrive over time and batches are allowed limited restarts. Any batch that contains a job which has already been restarted once cannot be restarted any more. We provide a best possible on-line algorithm for the problem with a competitive ratio .     

An improved on-line algorithm for scheduling on two unrestrictive parallel batch processing machines

We consider the problem of on-line scheduling a set of n jobs on two parallel batch processing machines. The objective is to minimize the makespan. We provide an algorithm for the problem that is better than one given in the literature, improving the competitive ratio from to .     

Competitive analysis of a dispatch policy for a dynamic multi-period routing problem

We analyze an on-line algorithm (dispatch policy) for a dynamic multi-period routing problem. The objective is to minimize the total cost over all periods. We show that the competitive ratio of this policy for instances with customers located on the non-negative real line is .     

The logarithmic derivative of areally mean p-valent functions

Let denote the class of functions f which are areally mean p-valent and have k maximal growth directions in Δ={z:|z|<1}. In this paper we give an asymptotic formula of the mean square of the logarithmic derivative f′/f for with some restricted condition. This generalizes the corresponding result in [J. Anal. Math. 36 (1979) 36-43]. Also we construct a function which does not satisfy this asymptotic formula.     

Linear information versus function evaluations for -approximation

We study algorithms for the approximation of functions, the error is measured in an L₂ norm. We consider the worst case setting for a general reproducing kernel Hilbert space of functions. We analyze algorithms that use standard information consisting in n function values and we are interested in the optimal order of convergence. This is the maximal exponent b for which the worst case error of such an algorithm is of order n^-b.Let p be the optimal order of convergence of all algorithms that may use arbitrary linear functionals, in contrast to function values only. So far it was not known whether p>b is possible, i.e., whether the approximation numbers or linear widths can be essentially smaller than the sampling numbers. This is (implicitly) posed as an open problem in the recent paper [F.Y. Kuo, G.W. Wasilowski, H. Woźniakowski, On the power of standard information for multivariate approximation in the worst case setting, J. Approx. Theory, to appear] where the authors prove that implies . Here we prove that the case and b=0 is possible, hence general linear information can be exponentially better than function evaluation. Since the case is quite different, it is still open whether b=p always holds in that case.     

The asymptotic representations on the norm of the Fourier operators

In this paper by a new method we first get . Based on it, we then obtain a new asymptotic representation on the norm Ln of the Fourier operators as follows: .     

Worst-case analysis of the subset sum algorithm for bin packing

We analyze the worst-case ratio of a natural heuristic for the bin packing problem, which proceeds by filling one bin at a time, each as much as possible. We show a nontrivial upper bound on this ratio of , almost matching a known lower bound.     

Tail asymptotic results for elliptical distributions

Let (X,Y) be a bivariate elliptical random vector with associated random radius in the Gumbel max-domain of attraction. In this paper we obtain a second order asymptotic expansion of the joint survival probability and the conditional probability , for x,y large.     

Tail behavior of random sums of negatively associated increments

Let be a sequence of negatively associated random variables with a common distribution function and finite expectation and let τ be a nonnegative integer-valued random variable independent of . In this paper we give unified form for the asymptotic behavior of the random sums in the case of . The results extend the earlier results of Aleškevi?iené et al. (2008) [2].     

Tighter bounds of the First Fit algorithm for the bin-packing problem

In this paper, we present improved bounds for the First Fit algorithm for the bin-packing problem. We prove for all lists L, and the absolute performance ratio of FF is at most .     

Optimal on-line flow time with resource augmentation

We study the problem of scheduling n jobs that arrive over time. We consider a non-preemptive setting on a single machine. The goal is to minimize the total flow time. We use extra resource competitive analysis: an optimal off-line algorithm which schedules jobs on a single machine is compared to a more powerful on-line algorithm that has ? machines. We design an algorithm of competitive ratio , where Δ is the maximum ratio between two job sizes, and provide a lower bound which shows that the algorithm is optimal up to a constant factor for any constant ?. The algorithm works for a hard version of the problem where the sizes of the smallest and the largest jobs are not known in advance, only Δ and n are known. This gives a trade-off between the resource augmentation and the competitive ratio.We also consider scheduling on parallel identical machines. In this case the optimal off-line algorithm has m machines and the on-line algorithm has ?m machines. We give a lower bound for this case. Next, we give lower bounds for algorithms using resource augmentation on the speed. Finally, we consider scheduling with hard deadlines, and scheduling so as to minimize the total completion time.     

Asymptotic expansions of Mellin convolution integrals: An oscillatory case

In a recent paper [J.L. López, Asymptotic expansions of Mellin convolution integrals, SIAM Rev. 50 (2) (2008) 275-293], we have presented a new, very general and simple method for deriving asymptotic expansions of for small x. It contains Watson’s Lemma and other classical methods, Mellin transform techniques, McClure and Wong’s distributional approach and the method of analytic continuation used in this approach as particular cases. In this paper we generalize that idea to the case of oscillatory kernels, that is, to integrals of the form , with c∈R, and we give a method as simple as the one given in the above cited reference for the case c=0. We show that McClure and Wong’s distributional approach for oscillatory kernels and the summability method for oscillatory integrals are particular cases of this method. Some examples are given as illustration.     

Randomized on-line scheduling on three processors

We consider a randomized on-line scheduling problem where each job has to be scheduled on any of m identical processors. The objective is to minimize the expected makespan. We show that the competitive ratio of any randomized algorithm for m=3 processors must be strictly greater than .