Spelling suggestions: "subject:"monotonic functions"" "subject:"monotonico functions""
1 
Monotone regression functionsZuo, Yanling January 1990 (has links)
In some applications, we require a monotone estimate of a regression function. In others, we want to test whether the regression function is monotone. For solving the first problem, Ramsay's, Kelly and Rice's, as well as pointwise monotone regression
functions in a spline space are discussed and their properties developed. Three monotone estimates are defined: leastsquare regression splines, smoothing splines and binomial regression splines. The three estimates depend upon a "smoothing parameter":
the number and location of knots in regression splines and the usual [formula omitted] in smoothing splines. Two standard techniques for choosing the smoothing parameter, GCV and AIC, are modified for monotone estimation, for the normal errors case. For answering the second question, a test statistic is proposed and its null distribution conjectured. Simulations are carried out to check the conjecture. These techniques are applied to two data sets. / Science, Faculty of / Statistics, Department of / Graduate

2 
Towards improved algorithms for testing bipartiteness and monotonicity.January 2013 (has links)
Alon 和Krivelevich (SIAM J. Discrete Math. 15(2): 211227 (2002)) 證明了如果一個圖是ε 非二部圖，那麼階數為Ỡ(1/ε) 的隨機導出于圖以很大概率是非二部圖。我們進一步猜想，這個導出子圖以很大概率是Ω(ε)非二部圖。Gonen 和Ron (RANDOM 2007) 證明了當圖的最大度不超過O (εn )時猜想成立。我們將對更一般的情形給出證明，對於任意d，所有d 正則(或幾乎d 正則)的圖猜想成立。 / 假設猜想成立的情況下，我們證明二分屬性是可以被單側誤差在O(1/ε^c ) 時間內檢驗的，其中c 是一個嚴格小於2 的常數，而這個結果也改進了Alon 和Krivelevich 的檢驗算法。由於己知對二分屬性的非適應性的檢驗算法需要Ω(1 /ε²) 的複雜性(Bogdanov 和Trevisan ， CCC 2004) ，我們的結果也得出，假設猜想成立，適應性對檢驗二分屬性是有幫助的。 / 另外一個有很多屬性檢驗問題被廣泛研究的領域是布爾函數。對布爾函數單調性的檢驗也是屬性檢驗的經典問題。給定對布爾函數f: {0,1}{U+207F} → {0,1} 的訪問，在[18]中，證明了檢驗算法複雜性的下界是Ω(√n) 。另一方面，在[21]中，作者們構造了一個複雜性為O(n) 的算法。在本文中，我們刻畫一些單調布爾函數的本質，設計算法并分析其對於一些困難例子的效果。最近，在[14] 中， 一個類似的算法被證明是非適應性，單側誤差，複雜性為Ỡ (n⁵/⁶ ε⁻⁵/³) 的算法。 / Alon and Krivelevich (SIAM J. Discrete Math. 15(2): 211227 (2002)) show that if a graph is εfar from bipartite, then the subgraph induced by a random subset of Ỡ (1/ε) vertices is not bipartite with high probability. We conjecture that the induced subgraph is Ω(ε)far from bipartite with high probability. Gonen and Ron (RANDOM 2007) proved this conjecture in the case when the degrees of all vertices are at most O(εn). We give a more general proof that works for any dregular (or almost dregular) graph for arbitrary degree d. / Assuming this conjecture, we prove that bipartiteness is testable with onesided error in time O(1=ε{U+1D9C}), where c is a constant strictly smaller than two, improving upon the tester of Alon and Krivelevich. As it is known that nonadaptive testers for bipartiteness require Ω(1/ε²) queries (Bogdanov and Trevisan, CCC2004), our result shows, assuming the conjecture, that adaptivity helps in testing bipartiteness. / The other area in which various properties have been well studied is boolean function. Testing monotonicity of Boolean functions is a classical question in property testing. Given oracle access to a Boolean function f : {0, 1}{U+207F} →{0, 1}, in [18], it is shown a lower bound of testing is Ω(√n). On the other hand, in [21], the authors introduced an algorithm to test monotonicity using O(n) queries. In this paper, we characterize some nature of monotone functions, design a tester and analyze the performance on some generalizations of the hard case. Recently, in [14], a similar tester is shown to be a nonadaptive, onesided error tester making Ỡ (n⁵/⁶ ε⁻⁵/³) queries. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Li, Fan. / Thesis (M.Phil.)Chinese University of Hong Kong, 2013. / Includes bibliographical references (leaves 7679). / Abstracts also in Chinese. / Abstract  p.i / Chapter 1  Introduction  p.1 / Chapter 1.1  Property Testing  p.1 / Chapter 1.2  Testing Bipartiteness  p.4 / Chapter 1.3  Testing Monotonicity  p.7 / Chapter 2  Testing Bipartiteness  p.11 / Chapter 2.1  Background  p.11 / Chapter 2.1.1  Our result  p.11 / Chapter 2.1.2  The algorithms of Gonen and Ron  p.13 / Chapter 2.1.3  Our proof  p.16 / Chapter 2.1.4  Notation  p.19 / Chapter 2.2  Splitting the vertices by degree  p.19 / Chapter 2.3  The algorithm for high degree vertices  p.20 / Chapter 2.4  Eliminating the high degree vertices  p.22 / Chapter 2.5  From an XOR game to a bipartite graph  p.33 / Chapter 2.6  Proof of the main theorem  p.35 / Chapter 2.7  Proof of the conjecture for regular graphs  p.37 / Chapter 3  Testing Monotonicity  p.40 / Chapter 3.1  Towards an improved tester  p.40 / Chapter 3.1.1  Properties of Distribution D  p.42 / Chapter 3.1.2  An Alternative Representation of D  p.46 / Chapter 3.1.3  Performance of D on Decreasing Functions  p.51 / Chapter 3.1.4  Functions Containing Ω(2{U+207F}) Disjoint Violating Edges  p.54 / Chapter 3.2  A o(n) Monotonicity Tester [14] and Some Improvements  p.62 / Chapter 3.2.1  A o(n) Monotonicity Tester [14]  p.62 / Chapter 3.2.2  An Alternative Proof of Theorem 3.2.2  p.65 / Chapter 4  Other Related Results  p.67 / Chapter 4.1  Short Odd Cycles in Graphs that are Far From Bipartiteness  p.67 / Chapter 4.2  Fourier Analysis on Boolean Functions  p.69 / Bibliography  p.76

3 
Simultaneous statistical inference for monotone doseresponse means /Liu, Lin, January 2001 (has links)
Thesis (Ph.D.)Memorial University of Newfoundland, 2001. / Restricted until November 2003. Bibliography: leaves 170178.

4 
Global optimization of monotonic programs applications in polynomial and stochastic programming /Cheon, MyunSeok. January 2005 (has links) (PDF)
Thesis (Ph. D.)Industrial & Systems Engineering, Georgia Institute of Technology, 2005. / Barnes, Earl, Committee Member ; Shapiro, Alex, Committee Member ; Realff, Matthew, Committee Member ; AlKhayyal, Faiz, Committee Chair ; Ahmed, Shabbir, Committee CoChair. Includes bibliographical references.

5 
Toward optimal tree construction of monotone functionsChen, Miao. Unknown Date (has links)
Thesis (M.S.)Duquesne University, 2005. / Title from document title page. Abstract included in electronic submission form. Includes bibliographical references (p. 21) and index.

6 
Monotonic tree and its application to multimedia information retrievalSong, Yuking. January 1900 (has links)
Thesis (Ph. D.)State University of New York at Buffalo, 2002. / Includes bibliographical references (p. 167186). Also available in print.

7 
The application of the inclusionexclusion principle in learning monotone boolean functionsGaffney, Christopher T., January 2008 (has links)
Thesis (M.S.)University of Nevada, Reno, 2008. / "May, 2008." Includes bibliographical references (leaves 6364). Online version available on the World Wide Web.

8 
A semiparametric approach to estimating item response functionsLiang, Longjuan, January 2007 (has links)
Thesis (Ph. D.)Ohio State University, 2007. / Title from first page of PDF file. Includes bibliographical references (p. 116120).

9 
Singlyconstrained monotropic network flow problems : a linear time transformation to unconstrained problems and qualitative sensitivity analysisGautier, Antoine January 1990 (has links)
This thesis examines several problems related to singlyconstrained Monotropic Network Flow Problems. In the first part, a linear time algorithm that reduces the solution of a monotropic network flow problem with an additional linear equality constraint to the solution of lower dimensional subproblems is presented. Of the subproblems, at most one is a singlyconstrained monotropic network flow problem while the others are unconstrained. If none of the subproblems is constrained, the algorithm provides a lineartime transformation of constrained to unconstrained monotropic network flow problems. Extensions to nonlinear and inequality constraints are given.
In the second part the qualitative theory of sensitivity analysis for Unconstrained MinimumCost Flow Problems presented by Granot and Veinott [GV85] is extended to MinimumCost Flow Problems with one additional linear constraint. The departure from the unconstrained network structure is shown to have a profound effect on computational issues. Two natural
extensions of the "lessdependenton" partial ordering of the arcs given in [GV85] are presented. One is decidable in linear time while the other yields more information but is NPcomplete in general. The Ripple Theorem gives upper bounds on the absolute value of optimalflow variations as a function of variations in the problem parameter. Moreover, it shows how changes may "ripple down" throughout the network, decreasing in magnitude as one gets "further away" from the arc whose parameter initiated the change. The Theory of Substitutes and Complements presents necessary and sufficient conditions for optimalflow changes to consistently have the same (or the opposite) sign in two given arcs. The complexity
of determining Substitutes and Complements is shown to be NPcomplete in general. However, for all intractable problems, families of cases arise from easily recognizable graph structures and can be computed in linear time. The Monotonicity Theory links the changes in the value of the parameters to the change in the optimal arcflows. Bounds on the rates
of changes are discussed.
We further provide a number of practical situations where our theory may apply. We discuss some MultiPeriod MultiProduct InventoryProduction models that can be formulated
as nonlinear parametric network flow problems with one additional linear constraint. We then apply our theory to help decision makers understand qualitatively how to respond to changes in the environment such as machine breakdown, strike or variations in inventory carrying costs without additional computation. In a second example, we show how a CashFlow Management model can be formulated as a nonlinear parametric network flow problem with one additional linear constraint. The theory is then recommended as a method by which a decision maker could understand qualitatively how to respond to changes in the environment such as variations in interest rates, taxes or asset prices without any additional computation. / Business, Sauder School of / Graduate

10 
New Methods in Sublinear Computation for High Dimensional ProblemsWaingarten, Erik Alex January 2020 (has links)
We study two classes of problems within sublinear algorithms: data structures for approximate nearest neighbor search, and property testing of Boolean functions. We develop algorithmic and analytical tools for proving upper and lower bounds on the complexity of these problems, and obtain the following results:
* We give data structures for approximate nearest neighbor search achieving stateoftheart approximations for various highdimensional normed spaces. For example, our data structure for 𝘢𝘳𝘣𝘪𝘵𝘳𝘢𝘳𝘺 normed spaces over R𝘥 answers queries in sublinear time while using nearly linear space and achieves approximation which is subpolynomial in the dimension.
* We prove query complexity lower bounds for property testing of three fundamental properties: 𝘬juntas, monotonicity, and unateness. Our lower bounds for nonadaptive junta testing and adaptive unateness testing are nearly optimal, and the lower bound for adaptive monotonicity testing is the best that is currently known.
* We give an algorithm for testing unateness with nearly optimal query complexity. The algorithm is crucially adaptive and based on a novel analysis of binary search over long paths of the hypercube.

Page generated in 0.1247 seconds