Search results for "lower bound"
showing 10 items of 269 documents
On n–Fold Blocking Sets
1986
An n-fold blocking set is a set of n-disjoint blocking sets. We shall prove upper and lower bounds for the number of components in an n-fold blocking set in projective and affine spaces.
Lower Bounds and Hierarchies for Quantum Memoryless Communication Protocols and Quantum Ordered Binary Decision Diagrams with Repeated Test
2017
We explore multi-round quantum memoryless communication protocols. These are restricted version of multi-round quantum communication protocols. The “memoryless” term means that players forget history from previous rounds, and their behavior is obtained only by input and message from the opposite player. The model is interesting because this allows us to get lower bounds for models like automata, Ordered Binary Decision Diagrams and streaming algorithms. At the same time, we can prove stronger results with this restriction. We present a lower bound for quantum memoryless protocols. Additionally, we show a lower bound for Disjointness function for this model. As an application of communicatio…
Real Line Arrangements and Surfaces with Many Real Nodes
2008
A long standing question is if the maximum number μ(d) of nodes on a surface of degree d in P( ) can be achieved by a surface defined over the reals which has only real singularities. The currently best known asymptotic lower bound, μ(d) 5 12 d, is provided by Chmutov’s construction from 1992 which gives surfaces whose nodes have non-real coordinates. Using explicit constructions of certain real line arrangements we show that Chmutov’s construction can be adapted to give only real singularities. All currently best known constructions which exceed Chmutov’s lower bound (i.e., for d = 3, 4, . . . , 8, 10, 12) can also be realized with only real singularities. Thus, our result shows that, up t…
Frequency Assignment and Multicoloring Powers of Square and Triangular Meshes
2005
The static frequency assignment problem on cellular networks can be abstracted as a multicoloring problem on a weighted graph, where each vertex of the graph is a base station in the network, and the weight associated with each vertex represents the number of calls to be served at the vertex. The edges of the graph model interference constraints for frequencies assigned to neighboring stations. In this paper, we first propose an algorithm to multicolor any weighted planar graph with at most $\frac{11}{4}W$ colors, where W denotes the weighted clique number. Next, we present a polynomial time approximation algorithm which garantees at most 2W colors for multicoloring a power square mesh. Fur…
Online Scheduling of Task Graphs on Heterogeneous Platforms
2020
Modern computing platforms commonly include accelerators. We target the problem of scheduling applications modeled as task graphs on hybrid platforms made of two types of resources, such as CPUs and GPUs. We consider that task graphs are uncovered dynamically, and that the scheduler has information only on the available tasks, i.e., tasks whose predecessors have all been completed. Each task can be processed by either a CPU or a GPU, and the corresponding processing times are known. Our study extends a previous $4\sqrt{m/k}$ 4 m / k -competitive online algorithm by Amaris et al. [1] , where $m$ m is the number of CPUs and $k$ k the number of GPUs ( $m\geq k$ m ≥ k ). We prove that no online…
A genetic system based on simulated crossover of sequences of two-bit genes
2006
AbstractWe introduce a genetic model based on simulated crossover of fixed sequences of two-bit genes. Results are(1)a lower bound on population size is exhibited such that a transition takes the stochastic finite population genetic system near the next state of the deterministic infinite population genetic system (provided both begin in the same state);(2)states and dynamics of the deterministic infinite population genetic system are derived for arbitrary (finite) fitness functions (expressed in terms of multivariate polynomials);(3)in the case of quadratic fitness defined by weight matrices with m nonnull entries it is shown that each state transition can be implemented in time O(m+l), wh…
A Branch-and-Cut method for the Capacitated Location-Routing Problem
2011
International audience; Recent researches in the design of logistic networks have shown that the overall distribution cost may be excessive if routing decisions are ignored when locating depots. The Location-Routing Problem (LRP) overcomes this drawback by simultaneously tackling location and routing decisions. The aim of this paper is to propose an exact approach based on a Branch-and-Cut algorithm for solving the LRP with capacity constraints on depots and vehicles. The proposed method is based on a zero-one linear model strengthened by new families of valid inequalities. The computational evaluation on three sets of instances (34 instances in total), with 5–10 potential depots and 20–88 …
Adaptive Finite-Time Control for a Flexible Hypersonic Vehicle with Actuator Fault
2013
The problem of robust fault-tolerant tracking control is investigated. Simulation on the longitudinal model of a flexible air-breathing hypersonic vehicle (FAHV) with actuator faults and uncertainties is conducted. In order to guarantee that the velocity and altitude track their desired commands in finite time with the partial loss of actuator effectiveness, an adaptive fault-tolerant control strategy is presented based on practical finite-time sliding mode method. The adaptive update laws are used to estimate the upper bound of uncertainties and the minimum value of actuator efficiency factor. Finally, simulation results show that the proposed control strategy is effective in rejecting unc…
Split-Delivery Capacitated Arc-Routing Problem: Lower Bound and Metaheuristic
2010
International audience; This paper proposes lower and upper bounds for the split-delivery capacitated arc-routing problem (SDCARP), a variant of the capacitated arc-routing problem in which an edge can be serviced by several vehicles. Recent papers on related problems in node routing have shown that this policy can bring significant savings. It is also more realistic in applications such as urban refuse collection, where a vehicle can become full in the middle of a street segment. This work presents the first lower bound for the SDCARP, computed with a cutting plane algorithm and an evolutionary local search reinforced by a multistart procedure and a variable neighborhood descent. Tests on …
Capacity Upper Bound of Channel Assembling in Cognitive Radio Networks with Quasistationary Primary User Activities
2013
In cognitive radio networks (CRNs) with multiple channels, various channel-assembling (ChA) strategies may be applied to secondary users (SUs), resulting in different achieved capacity. However, there is no previous work on determining the capacity upper bound (UB) of ChA for SUs under given system configurations. In this paper, we derive the maximum capacity for CRNs with ChA through Markov chain modeling, considering that primary user (PU) activities are relatively static, compared with SU services. We first deduce a closed-form expression for the maximum capacity in a dynamic ChA strategy and then demonstrate that no other ChA strategy can provide higher capacity than that achieved by th…