Optimization, block designs and No Free Lunch theorems

We study the precise conditions under which all optimization strategies for a given family of finite functions yield the same expected maximization performance, when averaged over a uniform distribution of the functions. In the case of bounded-length searches in a family of Boolean functions, we provide tight connections between such “No Free Lunch” conditions and the structure of t-designs and t-wise balanced designs for arbitrary values t. As a corollary, we obtain a nontrivial family of n-variate Boolean functions that satisfies the “No Free Lunch” condition with respect to searches of length Ω(n1/2/log1/2n). Modifying the construction, we also obtain nontrivial “No Free Lunch” families of functions with large ranges.     

A No Free Lunch theorem for multi-objective optimization

The No Free Lunch theorem (Schumacher et al., 2001; Wolpert and Macready, 1997 [8] and [10]) is a foundational impossibility result in black-box optimization stating that no optimization technique has performance superior to any other over any set of functions closed under permutation.This paper considers situations in which there is some form of structure on the set of objective values other than the typical total ordering (e.g., Pareto dominance in multi-objective optimization). It is shown that in such cases, when attention is restricted to natural measures of performance and optimization algorithms that measure performance and optimize with respect to this structure, that a No Free Lunch result holds for any class of problems which is structurally closed under permutation. This generalizes the Sharpened No Free Lunch theorem of Schumacher et al. (2001) [8] to non-totally ordered objective spaces.     

Simple Explanation of the No Free Lunch Theorem of Optimization

The No Free Lunch Theorem of Optimization (NFLT) is an impossibility theorem telling us that a general-purpose universal optimization strategy is impossible, and the only way one strategy can outperform another is if it is specialized to the structure of the specific problem under consideration. In this paper, a framework is presented for conceptualizing optimization problems that leads to useful insights and a simple explanation of the NFLT.     

On the longest increasing subsequence of a circular list

The longest increasing circular subsequence (LICS) of a list is considered. A Monte Carlo algorithm to compute it is given which has worst case execution time O(n3/2logn) and storage requirement O(n). It is proved that the expected length μ(n) of the LICS satisfies . Numerical experiments with the algorithm suggest that .     

A note on the search for k elements via quantum walk

In this paper we use the quantum walk search scheme by Magniez et al. (2007) [13] to find k solutions of a search problem. We show that the quantum query complexity is at most of order times the number of queries to find one solution.     

On the lexicographical generation of compressed codes

A certain class of algorithms for the lexicographical generation of combinatorial objects can be considered as working on the code tree representation of the objects processed. Then the strategy used by the algorithms in order to find lexicographical successors corresponds to a special kind of tree traversal. If the encoding used is redundant in the sense that the code tree has nodes with only one successor, compression becomes possible which allows for a speed-up in the lexicographical generation. In this note we analyze the average running time saved when compression is applied. For this purpose we consider random code trees within the model of simply generated trees together with the compression as used for the trie and the PATRICIA data structure. We prove general results which quantify the average savings only depending on the generator Θ and the size of the family under consideration. As an example, those results are applied to consider random encodings over an s-ary alphabet. Finally, we comment on connections of our findings to the problem of ranking words of a given language.     

On a compact encoding of the swap automaton

Given a string P of length m over an alphabet Σ of size σ, a swapped version of P is a string derived from P   by a series of local swaps, i.e., swaps of adjacent symbols, such that each symbol can participate in at most one swap. We present a theoretical analysis of the nondeterministic finite automaton for the language _?P′∈ΠPΣ^?P^′${?}_{P^{\prime }\in {\Pi }_P}{\Sigma }^{?}{P}^{\prime }$ (swap automaton, for short), where _ΠP${\Pi }_P$ is the set of swapped versions of P  . Our study is based on the bit-parallel simulation of the same automaton due to Fredriksson, and reveals an interesting combinatorial property that links the automaton to the one for the language Σ^?P${\Sigma }^{?}P$. By exploiting this property and the method presented by Cantone et al. (2012), we obtain a bit-parallel encoding of the swap automaton which takes O(σ²⌈k/w⌉)$O({\sigma }^2\lceil k/w\rceil )$ space and allows one to simulate the automaton on a string of length n   in time O(n⌈k/w⌉)$O(n\lceil k/w\rceil )$, where ⌈m/σ⌉?k?m$\lceil m/\sigma \rceil ?k?m$ is the size of a specific factorization of P defined by Cantone et al. (2012) and w is the word size in bits.     

The game chromatic number and the game colouring number of classes of oriented cactuses

We prove that the game chromatic and the game colouring number of the class of orientations of cactuses with girth of 2 or 3 is 4. We improve this bound for the class of orientations of certain forest-like cactuses to the value of 3. These results generalise theorems on the game colouring number of undirected forests (Faigle et al., 1993 [3]) resp. orientations of forests (Andres, 2009 [1]). For certain undirected cactuses with girth 4 we also obtain the tight bound 4, thus improving a result of Sidorowicz (2007) [8].     

Upper bound for the approximation ratio of a class of hypercube segmentation algorithms

The Hypercube Segmentation problem was recently introduced by Kleinberg et al. [J. ACM 51 (2004) 263-280], along with several algorithms that select each segment's prototype vector from the segment. The algorithms were shown to have an approximation ratio of at least . We show that a lemma used in this proof is tight, and that the asymptotic approximation ratio of no algorithm of this type can exceed 5/6≈0.833.     

Tight bounds on the number of minimum-mean cycle cancellations and related results

We prove a tight (min(nm log(nC), nm²)) bound on the number of iterations of the minimum-mean cycle-canceling algorithm of Goldberg and Tarjan [13]. We do this by giving the lower bound and by improving the strongly polynomial upper bound on the number of iterations toO(nm ²). We also give an improved version of the maximum-mean cut canceling algorithm of [7], which is a dual of the minimum-mean cycle-canceling algorithm. Our version of the dual algorithm runs in O(nm²) iterations.Partially supported by NSF Presidential Young Investigator Grant CCR-8858097 with matching funds provided by AT&T, IBM Faculty Development Award, and a grant from the 3M Corporation.     

On some properties of the NML estimator for Bernoulli strings

This paper proves the monotonicity of the sequence , where C_n denotes the normalization coefficient in the universal Normalized Maximum Likelihood (NML) model for the Bernoulli class. The main result is used to find a non-asymptotic estimation of logC_n.     

Loop-free Gray code algorithm for the e-restricted growth functions

The subject of Gray codes algorithms for the set partitions of {1,2,…,n} had been covered in several works. The first Gray code for that set was introduced by Knuth (1975) [5], later, Ruskey presented a modified version of Knuth?s algorithm with distance two, Ehrlich (1973) [3] introduced a loop-free algorithm for the set of partitions of {1,2,…,n}, Ruskey and Savage (1994) [9] generalized Ehrlich?s results and give two Gray codes for the set of partitions of {1,2,…,n}, and recently, Mansour et al. (2008) [7] gave another Gray code and loop-free generating algorithm for that set by adopting plane tree techniques.In this paper, we introduce the set of e-restricted growth functions (a generalization of restricted growth functions) and extend the aforementioned results by giving a Gray code with distance one for this set; and as a particular case we obtain a new Gray code for set partitions in restricted growth function representation. Our Gray code satisfies some prefix properties and can be implemented by a loop-free generating algorithm using classical techniques; such algorithms can be used as a practical solution of some difficult problems. Finally, we give some enumerative results concerning the restricted growth functions of order d.     

Proposal and validation of an optimization method using Monte Carlo method for multi-objective functions

Solving optimization problems is essential for many engineering applications and research tools. In a previous report, we proposed a new optimization method, MOST (Monte Carlo Stochastic Optimization), using the Monte Carlo method, and applied it to benchmark problems for optimization methods, and optimization of neural network machine learning. While the proposed method MOST was a single objective, this study is an extension of MOST so that it can be applied to multi-objective functions for the purpose of improving generality. As the verification, it was applied to the optimization problem with the restriction condition first, and it was also applied to the benchmark problem for the multi-objective optimization technique verification, and the validity was confirmed. For comparison, the calculation by genetic algorithm was also carried out, and it was confirmed that MOST was excellent in calculation accuracy and calculation time.     

On induced-universal graphs for the class of bounded-degree graphs

For a family F of graphs, a graph U is said to be F-induced-universal if every graph of F is an induced subgraph of U. We give a construction for an induced-universal graph for the family of graphs on n vertices with degree at most k. For k even, our induced-universal graph has O(nk/2) vertices and for k odd it has O(n⌈k/2⌉−1/klog2+2/kn) vertices. This construction improves a result of Butler by a multiplicative constant factor for the even case and by almost a multiplicative n1/k factor for the odd case. We also construct induced-universal graphs for the class of oriented graphs with bounded incoming and outgoing degree, slightly improving another result of Butler.     

Polynomial-time algorithms for probabilistic solutions of parameter-dependent linear matrix inequalities

A randomized approach is considered for a feasibility problem on a parameter-dependent linear matrix inequality (LMI). In particular, a gradient-based and an ellipsoid-based randomized algorithms are improved by introduction of a stopping rule. The improved algorithms stop after a bounded number of iterations and this bound is of polynomial order in the problem size. When the algorithms stop, either of the following two events occurs: (i) they find with high confidence a probabilistic solution, which satisfies the given LMI for most of the parameter values; (ii) they detect in an approximate sense the non-existence of a deterministic solution, which satisfies the given LMI for all the parameter values. These results are important because the original randomized algorithms have issues to be settled on detection of convergence, on the speed of convergence, and on the assumption of feasibility. The improved algorithms can be adapted for an optimization problem constrained by a parameter-dependent LMI. A numerical example shows the efficacy of the proposed algorithms.