Search results for "Bounded function"
showing 10 items of 508 documents
Stabilized branch-and-price algorithms for vector packing problems
2018
Abstract This paper considers packing and cutting problems in which a packing/cutting pattern is constrained independently in two or more dimensions. Examples are restrictions with respect to weight, length, and value. We present branch-and-price algorithms to solve these vector packing problems (VPPs) exactly. The underlying column-generation procedure uses an extended master program that is stabilized by (deep) dual-optimal inequalities. While some inequalities are added to the master program right from the beginning (static version), other violated dual-optimal inequalities are added dynamically. The column-generation subproblem is a multidimensional knapsack problem, either binary, boun…
Gray code for derangements
2004
AbstractWe give a Gray code and constant average time generating algorithm for derangements, i.e., permutations with no fixed points. In our Gray code, each derangement is transformed into its successor either via one or two transpositions or a rotation of three elements. We generalize these results to permutations with number of fixed points bounded between two constants.
Graph Rewriting Based Search for Molecular Structures: Definitions, Algorithms, Hardness
2018
We define a graph rewriting system that is easily understandable by humans, but rich enough to allow very general queries to molecule databases. It is based on the substitution of a single node in a node- and edge-labeled graph by an arbitrary graph, explicitly assigning new endpoints to the edges incident to the replaced node. For these graph rewriting systems, we are interested in the subgraph-matching problem. We show that the problem is NP-complete, even on graphs that are stars. As a positive result, we give an algorithm which is polynomial if both rules and query graph have bounded degree and bounded cut size. We demonstrate that molecular graphs of practically relevant molecules in d…
On the continuous and discontinuous maximal operators
2018
Abstract In the first part of this paper we study the regularity properties of a wide class of maximal operators. These results are used to show that the spherical maximal operator is continuous W 1 , p ( R n ) ↦ W 1 , p ( R n ) , when p > n n − 1 . Other given applications include fractional maximal operators and maximal singular integrals. On the other hand, we show that the restricted Hardy–Littlewood maximal operator M λ , where the supremum is taken over the cubes with radii greater than λ > 0 , is bounded from L p ( R n ) to W 1 , p ( R n ) but discontinuous.
Asymmetry matters: Dynamic half-way points in bidirectional labeling for solving shortest path problems with resource constraints faster
2017
Abstract With their paper “Symmetry helps: Bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints” [Discrete Optimization 3, 2006, pp. 255–273] Righini and Salani introduced bounded bidirectional dynamic programming (DP) as an acceleration technique for solving variants of the shortest path problem with resource constraints (SPPRC). SPPRCs must be solved iteratively when vehicle routing and scheduling problems are tackled via Lagrangian relaxation or column-generation techniques. Righini and Salani and several subsequent works have shown that bounded bidirectional DP algorithms are often superior to their monodirectional counterparts, s…
Packing colorings of subcubic outerplanar graphs
2018
Given a graph $G$ and a nondecreasing sequence $S=(s_1,\ldots,s_k)$ of positive integers, the mapping $c:V(G)\longrightarrow \{1,\ldots,k\}$ is called an $S$-packing coloring of $G$ if for any two distinct vertices $x$ and $y$ in $c^{-1}(i)$, the distance between $x$ and $y$ is greater than $s_i$. The smallest integer $k$ such that there exists a $(1,2,\ldots,k)$-packing coloring of a graph $G$ is called the packing chromatic number of $G$, denoted $\chi_{\rho}(G)$. The question of boundedness of the packing chromatic number in the class of subcubic (planar) graphs was investigated in several earlier papers; recently it was established that the invariant is unbounded in the class of all sub…
Varieties of algebras with pseudoinvolution and polynomial growth
2017
Let A be an associative algebra with pseudoinvolution (Formula presented.) over an algebraically closed field of characteristic zero and let (Formula presented.) be its sequence of (Formula presented.) -codimensions. We shall prove that such a sequence is polynomially bounded if and only if the variety generated by A does not contain five explicitly described algebras with pseudoinvolution. As a consequence, we shall classify the varieties of algebras with pseudoinvolution of almost polynomial growth, i.e. varieties of exponential growth such that any proper subvariety has polynomial growth and, along the way, we shall give also the classification of their subvarieties. Finally, we shall de…
Estimates for the differences of positive linear operators and their derivatives
2019
The present paper deals with the estimate of the differences of certain positive linear operators and their derivatives. Oxur approach involves operators defined on bounded intervals, as Bernstein operators, Kantorovich operators, genuine Bernstein-Durrmeyer operators, and Durrmeyer operators with Jacobi weights. The estimates in quantitative form are given in terms of the first modulus of continuity. In order to analyze the theoretical results in the last section, we consider some numerical examples.
On the existence of at least a solution for functional integral equations via measure of noncompactness
2017
In this article, we use fixed-point methods and measure of noncompactness theory to focus on the problem of establishing the existence of at least a solution for the following functional integral equation ¶ \[u(t)=g(t,u(t))+\int_{0}^{t}G(t,s,u(s))\,ds,\quad t\in{[0,+\infty[},\] in the space of all bounded and continuous real functions on $\mathbb{R}_{+}$ , under suitable assumptions on $g$ and $G$ . Also, we establish an extension of Darbo’s fixed-point theorem and discuss some consequences.
Ahlfors-regular distances on the Heisenberg group without biLipschitz pieces
2015
We show that the Heisenberg group is not minimal in looking down. This answers Problem 11.15 in `Fractured fractals and broken dreams' by David and Semmes, or equivalently, Question 22 and hence also Question 24 in `Thirty-three yes or no questions about mappings, measures, and metrics' by Heinonen and Semmes. The non-minimality of the Heisenberg group is shown by giving an example of an Ahlfors $4$-regular metric space $X$ having big pieces of itself such that no Lipschitz map from a subset of $X$ to the Heisenberg group has image with positive measure, and by providing a Lipschitz map from the Heisenberg group to the space $X$ having as image the whole $X$. As part of proving the above re…