Convergence of greedy algorithm in Walsh system in <Emphasis Type="Italic">L</Emphasis><Subscript><Emphasis Type="Italic">p</Emphasis></Subscript>

Convergence of the greedy algorithm in Walsh system in L _p , p > 1 is studied. It is proved that there exists a function in L _p , 1 < p < 2, with greedy algorithm not converging in measure to that function. A continuous function with divergent in L _p , p > 2, greedy algorithm is constructed and sufficient conditions for convergence of the greedy algorithm in L _p , p > 1 are given.     

Efficiency of weak greedy algorithms for m-term approximations

We investigate the efficiency of weak greedy algorithms for m-term expansional approximation with respect to quasi-greedy bases in general Banach spaces.We estimate the corresponding Lebesgue constants for the weak thresholding greedy algorithm(WTGA) and weak Chebyshev thresholding greedy algorithm.Then we discuss the greedy approximation on some function classes.For some sparse classes induced by uniformly bounded quasi-greedy bases of L_p,1p∞,we show that the WTGA realizes the order of the best m-term approximation.Finally,we compare the efficiency of the weak Chebyshev greedy algorithm(WCGA) with the thresholding greedy algorithm(TGA) when applying them to quasi-greedy bases in L_p,1≤p∞,by establishing the corresponding Lebesgue-type inequalities.It seems that when p2 the WCGA is better than the TGA.     

Frames and non linear approximations in Hilbert spaces

A simple proof of the proposition, stated in ([2], p. 346), asserting that in Hilbert spaces a Riesz basis is greedy, is given. Also, greedy approximant for frames in Hilbert spaces is defined and it is shown that frames satisfy the quasi greedy and almost greedy conditions. Finally, we give the characterizations of approximation spaces A^s(Ψ), A_q^s(Ψ) by means of weak-l_p and Lorentz sequence spaces for frames.     

Minimizing the Flow-time Variance in Single-machine Systems

In this paper we deal with an n-job, single-machine scheduling problem. All jobs are available from the start, and the objective is to minimize the variance of job flow-times. A heuristic procedure which is based on the complementary pair-exchange principle is proposed. It has been concluded that this heuristic procedure provides improved results (in terms of objective-function value) when compared with other heuristics. Our heuristic procedure has the complexity of O(n log n).     

An Optimal Heuristic For Coordinated Multi-Item Inventory Replenishments

The inventory control problem can be vastly simplified if the replenishments of inventory items are coordinated with one another. That is, whenever an item is replenished, n other items, where n is a decision variable, are also replenished. One way to ensure this would be to classify the inventory items into several groups with a common order interval for each group. In this paper we establish that the optimal groups will be consecutive by hD/A, where h, D and A are the holding cost, demand rate and set-up cost of an item respectively. Using this property of consecutiveness, we develop a fast converging heuristic to create m groups optimally, m = 2, 3,..., M. The heuristic is a substitute for the dynamic programme which would otherwise be necessary and it has the potential for nomographic applications.     

Two new heuristics for the <Emphasis Type="Italic">GI</Emphasis>/<Emphasis Type="Italic">G</Emphasis>/<Emphasis Type="Italic">n</Emphasis>/0 queueing loss system with examples based on the two-phase Coxian distribution

In this paper, we introduce a new heuristic approach for the numerical analysis of queueing systems. In particular, we study the general, multi-server queueing loss system, the GI/G/n/0 queue, with an emphasis on the calculation of steady-state loss probabilities. Two new heuristics are developed, called the GM Heuristic and the MG Heuristic, both of which make use of an exact analysis of the corresponding single-server GI/G/1/0 queue. The GM Heuristic also uses an exact analysis of the GI/M/n/0 queue, while the MG Heuristic uses an exact analysis of the M/G/n/0 queue. Experimental results are based on the use of two-phase Coxian distributions for both the inter-arrival time and the service time; these include an error analysis for each heuristic and the derivation of experimental probability bounds for the loss probability. For the class of problems studied, it is concluded that there are likely to be many situations where the accuracy of the GM Heuristic is adequate for practical purposes. Methods are also developed for combining the GM and MG Heuristics. In some cases, this leads to approximations that are significantly more accurate than those obtained by the individual heuristics.     

All Colors Shortest Path problem on trees

Given an edge weighted tree T(V, E), rooted at a designated base vertex \(r \in V\), and a color from a set of colors \(C=\{1,\ldots ,k\}\) assigned to every vertex \(v \in V\), All Colors Shortest Path problem on trees (ACSP-t) seeks the shortest, possibly non-simple, path starting from r in T such that at least one node from every distinct color in C is visited. We show that ACSP-t is NP-hard, and also prove that it does not have a constant factor approximation. We give an integer linear programming formulation of ACSP-t. Based on a linear programming relaxation of this formulation, an iterative rounding heuristic is proposed. The paper also explores genetic algorithm and tabu search to develop alternative heuristic solutions for ACSP-t. The performance of all the proposed heuristics are evaluated experimentally for a wide range of trees that are generated parametrically.     

Wavelets and Bidemocratic Pairs in Weighted Norm Spaces

A complete characterization of weight functions for which the higher-rank Haar wavelets are greedy bases in weighted L^p spaces is given. The proof uses the new concept of a bidemocratic pair for a Banach space and also pairs (Φ, Φ), where Φ is an orthonormal system of bounded functions in the spaces L^p, p≠2.     

On approximation of dominating tree in wireless sensor networks

We study the following problem: Given a weighted graph G = (V, E, w) with \({w: E \rightarrow \mathbb{Z}^+}\) , the dominating tree (DT) problem asks us to find a minimum total edge weight tree T such that for every \({v \in V}\) , v is either in T or adjacent to a vertex in T. To the best of our knowledge, this problem has not been addressed in the literature. Solving the DT problem can yield a routing backbone for broadcast protocols since (1) each node does not have to construct their own broadcast tree, (2) utilize the virtual backbone to reduce the message overhead, and (3) the weight of backbone representing the energy consumption is minimized. We prove the hardness of this problem, including the inapproximability result and present an approximation algorithm together with an efficient heuristic. Finally, we verify the effectiveness of our proposal through simulation.     

Lorentz Spaces and Embeddings Induced by Almost Greedy Bases in Banach Spaces

The aim of this paper is to undertake a systematic qualitative study of the built-in symmetry of almost greedy bases in Banach spaces. More specifically, by refining the techniques that Wojtaszczyk used in J Approx Theory 107(2), 293–314 2000 for quasi-greedy bases in Hilbert spaces, we show that an almost greedy basis in a Banach space X naturally induces embeddings that allow sandwiching X between two symmetric sequence spaces. Using classical interpolation techniques in combination with duality, we also explore what we label as interpolation of greedy bases. It is then proved that the only almost greedy basis shared by any two \(\ell _{p}\) spaces is equivalent to the standard unit vector basis and that there is no basis which is simultaneously (normalized and) greedy in two different \(L_{p}\) spaces. As a by-product of our work, we obtain a new characterization of greedy bases in Banach spaces in terms of bounded linear operators.     

An exact and heuristic approach for the <Emphasis Type="Italic">d</Emphasis>-minimum branch vertices problem

Given a connected graph \(G=(V,E)\), the d-Minimum Branch Vertices (d-MBV) problem consists in finding a spanning tree of G with the minimum number of vertices with degree strictly greater than d. We developed a Miller–Tucker–Zemlin based formulation with valid inequalities for this problem. The results obtained for different values of d show the effectiveness of the proposed method, which has solved several instances faster than previous methods. Also, an heuristic is proposed for this problem, that was tested on several instances of the Minimum Branch Vertices problem, which is the d-MBV problem, when \(d = 2\).     

New heuristics for flow shop problem to minimize makespan

This paper investigates the flow shop problem with the objective to minimizemakespan. New algorithms are designed: one is off-line heuristic, Single JobFirst, for problemF _m ∥C _max ;and the other is on-line heuristic, Dynamic Single Job First (DSJF), for problemF _m |r _i |C _max and its on-line version. It is proved that the two heuristics are asymptoticallyoptimal when the size of the problem is large enough. In addition, theasymptotical optimality of First-Come, First-Served manner is obtained as abyproduct of the asymptotical analysis of DSJF heuristic. At the end of thepaper, a new lower bound with performance guarantee is provided for problemF _m ∥C _max , andcomputational experiments show the effectiveness of these heuristicalgorithms.     

On the Fourier spectrum of symmetric Boolean functions

We study the following questionWhat is the smallest t such that every symmetric boolean function on κ variables (which is not a constant or a parity function), has a non-zero Fourier coefficient of order at least 1 and at most t?We exclude the constant functions for which there is no such t and the parity functions for which t has to be κ. Let τ (κ) be the smallest such t. Our main result is that for large κ, τ (κ)≤4κ/logκ.The motivation for our work is to understand the complexity of learning symmetric juntas. A κ-junta is a boolean function of n variables that depends only on an unknown subset of κ variables. A symmetric κ-junta is a junta that is symmetric in the variables it depends on. Our result implies an algorithm to learn the class of symmetric κ-juntas, in the uniform PAC learning model, in time n ^o(κ) . This improves on a result of Mossel, O’Donnell and Servedio in [16], who show that symmetric κ-juntas can be learned in time n ^2κ/3.     

Hyper-heuristics: a survey of the state of the art

Hyper-heuristics comprise a set of approaches that are motivated (at least in part) by the goal of automating the design of heuristic methods to solve hard computational search problems. An underlying strategic research challenge is to develop more generally applicable search methodologies. The term hyper-heuristic is relatively new; it was first used in 2000 to describe heuristics to choose heuristics in the context of combinatorial optimisation. However, the idea of automating the design of heuristics is not new; it can be traced back to the 1960s. The definition of hyper-heuristics has been recently extended to refer to a search method or learning mechanism for selecting or generating heuristics to solve computational search problems. Two main hyper-heuristic categories can be considered: heuristic selection and heuristic generation. The distinguishing feature of hyper-heuristics is that they operate on a search space of heuristics (or heuristic components) rather than directly on the search space of solutions to the underlying problem that is being addressed. This paper presents a critical discussion of the scientific literature on hyper-heuristics including their origin and intellectual roots, a detailed account of the main types of approaches, and an overview of some related areas. Current research trends and directions for future research are also discussed.     

Space of invariant bilinear forms

Let \({\mathbb {F}}\) be a field, V a vector space of dimension n over \({\mathbb {F}}\). Then the set of bilinear forms on V forms a vector space of dimension \(n^2\) over \({\mathbb {F}}\). For char \({\mathbb {F}}\ne 2\), if T is an invertible linear map from V onto V then the set of T-invariant bilinear forms, forms a subspace of this space of forms. In this paper, we compute the dimension of T-invariant bilinear forms over \({\mathbb {F}}\). Also we investigate similar type of questions for the infinitesimally T-invariant bilinear forms (T-skew symmetric forms). Moreover, we discuss the existence of nondegenerate invariant (resp. infinitesimally invariant) bilinear forms.     

Economic optimization in a fixed sequence of unreliable inspections

Given a fixed sequence of unreliable inspection operations with known costs and inspection error probabilities of two types (classifying good items as defective and vice versa), we develop a model for selecting the set of inspections that should be activated in order to minimize expected total costs (inspection and penalties). We present an efficient branch and bound algorithm for finding the optimal solution, and two variations of a greedy heuristic that can be applied jointly to provide very good solutions at a O(n²) computational complexity. The conclusions are backed by a factorial experiment that included 1440 problem instances.     

Fast heuristics for protection networks for dynamic routing

Traffic volatility and network reliability are important issues in the provision of high speed network services. We consider the construction of a second network, the protection network which can carry overload traffic due to the failure or congestion of any two links in the original network. The level of protection against such contingencies can be specified by a traffic requirement matrix. We construct a fully connected protection network, for an n node network, using an O(n²) heuristic based on the largest two traffic requirements for each node. This procedure is then modified to generate a more effective O(n⁴) heuristic, both methods facilitate fast processing for two-hop dynamic routing. We compare the performance of the heuristics with the O(n¹⁵) optimal solution.     

The independent neighborhoods process

A triangle T^(r) in an r-uniform hypergraph is a set of r+1 edges such that r of them share a common (r-1)-set of vertices and the last edge contains the remaining vertex from each of the first r edges. Our main result is that the random greedy triangle-free process on n points terminates in an r-uniform hypergraph with independence number O((n log n)^1/r). As a consequence, using recent results on independent sets in hypergraphs, the Ramsey number r(T^(r),K_s^(r)) has order of magnitude s^r/ log s. This answers questions posed in [4, 10] and generalizes the celebrated results of Ajtai–Komlós–Szemerédi [1] and Kim [9] to hypergraphs.     

Complexity of the satisfiability problem for multilinear forms over a finite field

Multilinear forms over finite fields are considered. Multilinear forms over a field are products in which each factor is the sum of variables or elements of this field. Each multilinear form defines a function over this field. A multilinear form is called satisfiable if it represents a nonzero function. We show the N P-completeness of the satisfiability recognition problem for multilinear forms over each finite field of q elements for q ≥ 3. A theorem is proved that distinguishes cases of polynomiality and NP-completeness of the satisfiability recognition problem for multilinear fields for each possible q ≥ 3.     

Heuristic Solution Methods for Two Location Problems with Unreliable Facilities

In this paper, the p-median and p-centre problems are generalized by considering the possibility that one or more of the facilities may become inactive. The unreliable p-median problem is defined by introducing the probability that a facility becomes inactive. The (p, q)-centre problem is defined when p facilities need to be located but up to q of them may become unavailable at the same time. An heuristic procedure is presented for each problem. A rigorous procedure is discussed for the (p, q)-centre problem. Computational results are presented.