Search results for "Operation"
showing 10 items of 2969 documents
The Descriptive Complexity Approach to LOGCFL
1998
Building upon the known generalized-quantifier-based first-order characterization of LOGCFL, we lay the groundwork for a deeper investigation. Specifically, we examine subclasses of LOGCFL arising from varying the arity and nesting of groupoidal quantifiers. Our work extends the elaborate theory relating monoidal quantifiers to NC1 and its subclasses. In the absence of the BIT predicate, we resolve the main issues: we show in particular that no single outermost unary groupoidal quantifier with FO can capture all the context-free languages, and we obtain the surprising result that a variant of Greibach's ``hardest context-free language'' is LOGCFL-complete under quantifier-free BIT-free proj…
Scalability of using Restricted Boltzmann Machines for Combinatorial Optimization
2014
Abstract Estimation of Distribution Algorithms (EDAs) require flexible probability models that can be efficiently learned and sampled. Restricted Boltzmann Machines (RBMs) are generative neural networks with these desired properties. We integrate an RBM into an EDA and evaluate the performance of this system in solving combinatorial optimization problems with a single objective. We assess how the number of fitness evaluations and the CPU time scale with problem size and complexity. The results are compared to the Bayesian Optimization Algorithm (BOA), a state-of-the-art multivariate EDA, and the Dependency Tree Algorithm (DTA), which uses a simpler probability model requiring less computati…
Unbiased Estimators and Multilevel Monte Carlo
2018
Multilevel Monte Carlo (MLMC) and unbiased estimators recently proposed by McLeish (Monte Carlo Methods Appl., 2011) and Rhee and Glynn (Oper. Res., 2015) are closely related. This connection is elaborated by presenting a new general class of unbiased estimators, which admits previous debiasing schemes as special cases. New lower variance estimators are proposed, which are stratified versions of earlier unbiased schemes. Under general conditions, essentially when MLMC admits the canonical square root Monte Carlo error rate, the proposed new schemes are shown to be asymptotically as efficient as MLMC, both in terms of variance and cost. The experiments demonstrate that the variance reduction…
Classical automata on promise problems
2015
Promise problems were mainly studied in quantum automata theory. Here we focus on state complexity of classical automata for promise problems. First, it was known that there is a family of unary promise problems solvable by quantum automata by using a single qubit, but the number of states required by corresponding one-way deterministic automata cannot be bounded by a constant. For this family, we show that even two-way nondeterminism does not help to save a single state. By comparing this with the corresponding state complexity of alternating machines, we then get a tight exponential gap between two-way nondeterministic and one-way alternating automata solving unary promise problems. Secon…
Fractal surfaces from simple arithmetic operations
2015
Fractal surfaces ('patchwork quilts') are shown to arise under most general circumstances involving simple bitwise operations between real numbers. A theory is presented for all deterministic bitwise operations on a finite alphabet. It is shown that these models give rise to a roughness exponent $H$ that shapes the resulting spatial patterns, larger values of the exponent leading to coarser surfaces.
Isotonic regression for metallic microstructure data: estimation and testing under order restrictions
2021
Investigating the main determinants of the mechanical performance of metals is not a simple task. Already known physical inspired qualitative relations between 2D microstructure characteristics and 3D mechanical properties can act as the starting point of the investigation. Isotonic regression allows to take into account ordering relations and leads to more efficient and accurate results when the underlying assumptions actually hold. The main goal in this paper is to test order relations in a model inspired by a materials science application. The statistical estimation procedure is described considering three different scenarios according to the knowledge of the variances: known variance ra…
General framework for testing Poisson-Voronoi assumption for real microstructures
2020
Modeling microstructures is an interesting problem not just in Materials Science but also in Mathematics and Statistics. The most basic model for steel microstructure is the Poisson-Voronoi diagram. It has mathematically attractive properties and it has been used in the approximation of single phase steel microstructures. The aim of this paper is to develop methods that can be used to test whether a real steel microstructure can be approximated by such a model. Therefore, a general framework for testing the Poisson-Voronoi assumption based on images of 2D sections of real metals is set out. Following two different approaches, according to the use or not of periodic boundary conditions, thre…
Defining and measuring the network flexibility of humanitarian supply chains: insights from the 2015 Nepal earthquake
2019
International audience; The efficient and effective response to disasters critically depends on humanitarian supply chains (HSCs). HSCs need to be flexible to adapt to uncertainties in needs, infrastructure conditions, and behavior of other organizations. The concept of ‘network flexibility’ is, however, not clearly defined. The lack of an unanimous definition has led to a lack of consistent understanding and comparisons. This paper makes a threefold contribution: first, it defines the concept of network flexibility for HSC in the context of sudden onset disasters. Second, it proposes a framework to measure network flexibility in HSCs. Third, we apply our framework to the 2015 Nepal earthqu…
The General Routing Problem polyhedron: Facets from the RPP and GTSP polyhedra
1998
[EN] In this paper we study the polyhedron associated with the General Routing Problem (GRP). This problem, first introduced by Orloff in 1974, is a generalization of both the Rural Postman Problem (RPP) and the Graphical Traveling Salesman Problem (GTSP) and, thus, is NP -hard. We describe a formulation of the problem such that from every non-trivial facet-inducing inequality for the RPP and GTSP polyhedra, we obtain facet-inducing inequalities for the GRP polyhedron, We describe a new family of facet-inducing inequalities for the GRP, the honeycomb constraints, which seem to be very useful for solving GRP and RPP instances. Finally, new classes of facets obtained by composition of facet-i…
Market entry decisions of US small and medium‐sized software firms
2008
PurposeThe purpose of this paper is to investigate market entry decisions of the US software SMEs by analyzing the impact of the most obvious factors (cultural distance, geographical distance, country risk, and three market size variables) in traditional internationalization theories to target country selection. By investigating the influence of these commonly cited macro‐level factors, this study proposes the best indicator for market entry decisions of the US small and medium‐sized software firms.Design/methodology/approachThis study uses a quantitative research approach applied to a sample of 100 US small and medium‐sized software firms.FindingsEmpirical findings in this study indicate t…