Browsing by Subject "Dynamic programming"

Sort by: Order: Results:

Now showing items 1-5 of 5
  • Iho, Antti (Helsingin yliopisto, taloustieteen laitos, 2007)
    Julkaisuja
    Eutrophication of surface waters accelerated by nutrient runoff from agriculture is a growing concern in developed countries. Controlling the loss of phosphorus is complicated, among other things, due to its intertemporal nature. Phosphorus fertilisation affects crop yields and phosphorus losses mainly via the potentially plant available of soil phosphorus reserves whose development is very slow. Hence, both privately and socially optimal choices of phosphorus are results of a dynamic decision making process. On the other hand, phosphorus loss is comprised of various phosphorus forms, differing in their contribution to eutrophication and in their sensitivity towards various phosphorus control measures. These forms can be roughly divided into particulate phosphorus and dissolved reactive phosphorus. The former can be controlled mainly by controlling the soil erosion, the latter by controlling the potentially plant available soil phosphorus reserves. In this study, we solve analytically the privately and socially optimal steady state fertilisation levels and vegetative filter strip allocations, and design and analyse alternative instruments to sustain these allocations. We conduct an empirical application for an agricultural area of 37 parcels of one hectare, varying in their slopes and shapes. We find that the first-best taxes can be equivalently base on fertilisation or on soil phosphorus, but basing them directly on soil phosphorus might reduce the information burden of the regulator. We also find that the vegetative filter strip allocations are strongly differentiated, and that the second-best vegetative filter strip subsidies can be relatively easily be adjusted to sustain almost the first-best allocations.
  • Rizzi, Romeo; Tomescu, Alexandru I. (2019)
    In the #P-complete problem of counting 0/1 Knapsack solutions, the input consists of a sequence of n nonnegative integer weights w1,…,wn and an integer C, and we have to find the number of subsequences (subsets of indices) with total weight at most C. We give faster and simpler fully polynomial-time approximation schemes (FPTASes) for this problem, and for its random generation counterpart. Our method is based on dynamic programming and discretization of large numbers through floating-point arithmetic. We improve both deterministic counting FPTASes from Gopalan et al. (2011) [9], Štefankovič et al. (2012) [6] and the randomized counting and random generation algorithms in Dyer (2003) [5]. Our method is general, and it can be directly applied on top of combinatorial decompositions (such as dynamic programming solutions) of various problems. For example, we also improve the complexity of the problem of counting 0/1 Knapsack solutions in an arc-weighted DAG.
  • Norri, Tuukka; Cazaux, Bastien; Kosolobov, Dmitry; Mäkinen, Veli (BioMed Central, 2019)
    Abstract Background  We study a preprocessing routine relevant in pan-genomic analyses: consider a set of aligned haplotype sequences of complete human chromosomes. Due to the enormous size of such data, one would like to represent this input set with a few founder sequences that retain as well as possible the contiguities of the original sequences. Such a smaller set gives a scalable way to exploit pan-genomic information in further analyses (e.g. read alignment and variant calling). Optimizing the founder set is an NP-hard problem, but there is a segmentation formulation that can be solved in polynomial time, defined as follows. Given a threshold L and a set $${\mathcal {R}} = \{R_1, \ldots , R_m\}$$ R = { R 1 , … , R m } of m strings (haplotype sequences), each having length n, the minimum segmentation problem for founder reconstruction is to partition [1, n] into set P of disjoint segments such that each segment $$[a,b] \in P$$ [ a , b ] ∈ P has length at least L and the number $$d(a,b)=|\{R_i[a,b] :1\le i \le m\}|$$ d ( a , b ) = | { R i [ a , b ] : 1 ≤ i ≤ m } | of distinct substrings at segment [a, b] is minimized over $$[a,b] \in P$$ [ a , b ] ∈ P . The distinct substrings in the segments represent founder blocks that can be concatenated to form $$\max \{ d(a,b) :[a,b] \in P \}$$ max { d ( a , b ) : [ a , b ] ∈ P } founder sequences representing the original $${\mathcal {R}}$$ R such that crossovers happen only at segment boundaries. Results  We give an O(mn) time (i.e. linear time in the input size) algorithm to solve the minimum segmentation problem for founder reconstruction, improving over an earlier $$O(mn^2)$$ O ( m n 2 ) . Conclusions  Our improvement enables to apply the formulation on an input of thousands of complete human chromosomes. We implemented the new algorithm and give experimental evidence on its practicality. The implementation is available in https://github.com/tsnorri/founder-sequences .
  • Norri, Tuukka; Cazaux, Bastien; Kosolobov, Dmitry; Mäkinen, Veli (2019)
    Background: We study a preprocessing routine relevant in pan-genomic analyses: consider a set of aligned haplotype sequences of complete human chromosomes. Due to the enormous size of such data, one would like to represent this input set with a few founder sequences that retain as well as possible the contiguities of the original sequences. Such a smaller set gives a scalable way to exploit pan-genomic information in further analyses (e.g. read alignment and variant calling). Optimizing the founder set is an NP-hard problem, but there is a segmentation formulation that can be solved in polynomial time, defined as follows. Given a threshold L and a set R={R1,...,Rm} of m strings (haplotype sequences), each having length n, the minimum segmentation problem for founder reconstruction is to partition [1,n] into set P of disjoint segments such that each segment [a,b]P has length at least L and the number d(a,b)=|{Ri[a,b]:1im}| of distinct substrings at segment [a,b] is minimized over [a,b]P. The distinct substrings in the segments represent founder blocks that can be concatenated to form max{d(a,b):[a,b]P} founder sequences representing the original R such that crossovers happen only at segment boundaries. Results: We give an O(mn) time (i.e. linear time in the input size) algorithm to solve the minimum segmentation problem for founder reconstruction, improving over an earlier O(mn2). Conclusions: Our improvement enables to apply the formulation on an input of thousands of complete human chromosomes. We implemented the new algorithm and give experimental evidence on its practicality. The implementation is available in https://github.com/tsnorri/founder-sequences.
  • Iho, Antti (Helsingin yliopisto, taloustieteen laitos, 2008)
    Discussion Papers
    We analyze optimal phosphorus fertilization and erosion control policies in a spatial, dynamic, stationary framework. First-best instruments to incentivize farmers to undertake the socially optimal choices are analyzed both analytically and empirically. The empirical application is conducted for a cereal production area of 4 hectares. We find that taxes on phosphorus use can equivalently be levied either on fertilizer use or directly on soil phosphorus. However, tax on soil phosphorus is simpler and poses lower information requirements for the social planner. Also, the potential differences in socially and privately applied discount rates are shown to affect optimal tax rates substantially.