Abstract. Let G be a graph with edge set E(G). S E(G) is called an edge cover of G ifevery vertex of G is an end vertex of some edges in S. The edge covering chromatic numberof a graph G, denoted by Xc(G) is the maxim...Abstract. Let G be a graph with edge set E(G). S E(G) is called an edge cover of G ifevery vertex of G is an end vertex of some edges in S. The edge covering chromatic numberof a graph G, denoted by Xc(G) is the maximum size of a partition of E(G) into edgecovers of G. It is known that for any graph G with minimum degree δ,δ- 1 The fractional edge covering chromatic number of a graph G, denoted by Xcf(G), is thefractional matching number of the edge covering hypergraph H of G whose vertices arethe edges of G and whose hyperedges the edge covers of G. In this paper, we studythe relation between X’c(G) and δ for any graph G, and give a new simple proof of theinequalities δ - 1 ≤ X’c(G) ≤ δ by the technique of graph coloring. For any graph G, wegive an exact formula of X’cf(G), that is,where A(G)=minand the minimum is taken over all noempty subsets S of V(G) and C[S] is the set of edgesthat have at least one end in S.展开更多
In this paper, we consider the relationship between the binding number and the existence of fractional k-factors of graphs. The binding number of G is defined by Woodall as bind(G)=min{ | NG(X) || X |:∅≠X⊆V(G) }. It ...In this paper, we consider the relationship between the binding number and the existence of fractional k-factors of graphs. The binding number of G is defined by Woodall as bind(G)=min{ | NG(X) || X |:∅≠X⊆V(G) }. It is proved that a graph G has a fractional 1-factor if bind(G)≥1and has a fractional k-factor if bind(G)≥k−1k. Furthermore, it is showed that both results are best possible in some sense.展开更多
This paper presents learning rates for the least-square regularized regression algorithms with polynomial kernels. The target is the error analysis for the regression problem in learning theory. A regularization schem...This paper presents learning rates for the least-square regularized regression algorithms with polynomial kernels. The target is the error analysis for the regression problem in learning theory. A regularization scheme is given, which yields sharp learning rates. The rates depend on the dimension of polynomial space and polynomial reproducing kernel Hilbert space measured by covering numbers. Meanwhile, we also establish the direct approximation theorem by Bernstein-Durrmeyer operators in $ L_{\rho _X }^2 $ with Borel probability measure.展开更多
In this paper we get some relations between α（G）, α＇（G）, β（G）, β＇（G） and αT（G）, βT（G）. And all bounds in these relations are best possible, where α（G）, α＇（G）,/3（G）, β（G）, αT（G） and ...In this paper we get some relations between α（G）, α＇（G）, β（G）, β＇（G） and αT（G）, βT（G）. And all bounds in these relations are best possible, where α（G）, α＇（G）,/3（G）, β（G）, αT（G） and βT（G） are the covering number, edge-covering number, independent number, edge-independent number （or matching number）, total covering number and total independent number, respectively.展开更多
Abstract A t-hyperwhesl （t 〉 3） of length l （or Wz（t） for brevity） is a t-uniform hypergraph （V, E）, where t E= {e1,e2,...,el} and vl,v2,...,vt are distinct vertices of V = Ui=1 ei such that for i= 1,...,1, ...Abstract A t-hyperwhesl （t 〉 3） of length l （or Wz（t） for brevity） is a t-uniform hypergraph （V, E）, where t E= {e1,e2,...,el} and vl,v2,...,vt are distinct vertices of V = Ui=1 ei such that for i= 1,...,1, vi,vi＋1 ∈ei and ei ∩ ej = P, j ∈ {i - 1, i,i ＋ 1}, where the operation on the subscripts is modulo 1 and P is a vertex of V which is different from vi, 1 〈 i 〈 l. In this paper, the minimum covering problem of MCλ（3, W（3）,v） is investigated. Direct and recursive constructions on MCλ（3, W（3）,v） are presented. The covering number cλ（3, W4（3）, v） is finally determined for any positive integers v 〉 5 and A.展开更多
The relations among the dominating number, independence number and covering number of hypergraphs are investigated. Main results are as follows：Dv（H）≤min{α≤（H）, p（H）, p（H）, T（H）}; De（H）≤min{v（H）, T...The relations among the dominating number, independence number and covering number of hypergraphs are investigated. Main results are as follows：Dv（H）≤min{α≤（H）, p（H）, p（H）, T（H）}; De（H）≤min{v（H）, T（H）, p（H）}; DT（H） ≤αT（H）; S（H）≤ Dv （H） ＋ α（H）≤n; 2≤ Dv （H） ＋ T（H） ≤n; 2 〈 Dv （H） ＋ v（H）≤n/2 ＋ [n/r]; Dv （H） ＋ p（H） 〈_n;2≤De（H） ＋ Dv（H）≤n/2 ＋ [n/r];α（H） ＋ De（H）≤n;2 ≤ De（H） ＋ v（H）≤2[n/r]; 2 De（H） ＋ p（H）≤n-r ＋ 2.展开更多
In geometry, there are several challenging problems studying numbers associated to convex bodies. For example, the packing density problem, the kissing number problem, the covering density problem, the packing-coverin...In geometry, there are several challenging problems studying numbers associated to convex bodies. For example, the packing density problem, the kissing number problem, the covering density problem, the packing-covering constant problem, Hadwiger＇s covering conjecture and Borsuk＇s partition conjecture. They are flmdamental and fascinating problems about the same objects. However, up to now, both the methodology and the technique applied to them are essentially different. Therefore, a common foundation for them has been much expected. By treating problems of these types as functionals defined on the spaces of n-dimensional convex bodies, this paper tries to create such a foundation. In particular, supderivatives for these functionals will be studied.展开更多
A standard assumption in the literature of learning theory is the samples which are drawn independently from an identical distribution with a uniform bounded output. This excludes the common case with Gaussian distrib...A standard assumption in the literature of learning theory is the samples which are drawn independently from an identical distribution with a uniform bounded output. This excludes the common case with Gaussian distribution. In this paper we extend these assumptions to a general case. To be precise, samples are drawn from a sequence of unbounded and non-identical probability distributions. By drift error analysis and Bennett inequality for the unbounded random variables, we derive a satisfactory learning rate for the ERM algorithm.展开更多
The paper deals with estimates of the covering number for some Mercer kernel Hilbert space with Bernstein-Durrmeyer operators. We first give estimates of l2- norm of Mercer kernel matrices reproducing by the kernelsK...The paper deals with estimates of the covering number for some Mercer kernel Hilbert space with Bernstein-Durrmeyer operators. We first give estimates of l2- norm of Mercer kernel matrices reproducing by the kernelsK（α,β）（x,y）：=∑∞k=0 Ck（α,β）（x）Qk（α,β）（y）,where Qk（α,β） （x） are the Jacobi polynomials of order k on （0, 1 ）, Ck（α,β） 〉 0 are real numbers, and from which give the lower and upper bounds of the covering number for some particular reproducing kernel Hilbert space reproduced by Kα,β （x, y）.展开更多
Partially observable Markov decision processes （POMDPs） provide a rich mathematical framework for planning tasks in partially observable stochastic environments. The notion of the covering number, a metric of captur...Partially observable Markov decision processes （POMDPs） provide a rich mathematical framework for planning tasks in partially observable stochastic environments. The notion of the covering number, a metric of capturing the search space size of a POMDP planning problem, has been proposed as a complexity measure of approximate POMDP planning. Existing theoretical results are based on POMDPs with finite and discrete state spaces and measured in the l1- metric space. When considering heuristics, they are assumed to be always admissible. This paper extends the theoretical results on the covering numbers of different search spaces, including the newly defined space reachable under inadmissible heuristics, to the ln-metric spaces. We provide a simple but scalable algorithm for estimating covering numbers. Experimentally, we provide estimated covering numbers of the search spaces reachable by following different policies on several benchmark problems, and analyze their abilities to predict the runtime of POMDP planning algorithms.展开更多
Semi-supervised learning is an emerging computational paradigm for machine learning,that aims to make better use of large amounts of inexpensive unlabeled data to improve the learning performance.While various methods...Semi-supervised learning is an emerging computational paradigm for machine learning,that aims to make better use of large amounts of inexpensive unlabeled data to improve the learning performance.While various methods have been proposed based on different intuitions,the crucial issue of generalization performance is still poorly understood.In this paper,we investigate the convergence property of the Laplacian regularized least squares regression,a semi-supervised learning algorithm based on manifold regularization.Moreover,the improvement of error bounds in terms of the number of labeled and unlabeled data is presented for the first time as far as we know.The convergence rate depends on the approximation property and the capacity of the reproducing kernel Hilbert space measured by covering numbers.Some new techniques are exploited for the analysis since an extra regularizer is introduced.展开更多
基金the National Natural Science Foundation the Doctoral Foundation of the Education Committee of China.
文摘Abstract. Let G be a graph with edge set E(G). S E(G) is called an edge cover of G ifevery vertex of G is an end vertex of some edges in S. The edge covering chromatic numberof a graph G, denoted by Xc(G) is the maximum size of a partition of E(G) into edgecovers of G. It is known that for any graph G with minimum degree δ,δ- 1 The fractional edge covering chromatic number of a graph G, denoted by Xcf(G), is thefractional matching number of the edge covering hypergraph H of G whose vertices arethe edges of G and whose hyperedges the edge covers of G. In this paper, we studythe relation between X’c(G) and δ for any graph G, and give a new simple proof of theinequalities δ - 1 ≤ X’c(G) ≤ δ by the technique of graph coloring. For any graph G, wegive an exact formula of X’cf(G), that is,where A(G)=minand the minimum is taken over all noempty subsets S of V(G) and C[S] is the set of edgesthat have at least one end in S.
文摘In this paper, we consider the relationship between the binding number and the existence of fractional k-factors of graphs. The binding number of G is defined by Woodall as bind(G)=min{ | NG(X) || X |:∅≠X⊆V(G) }. It is proved that a graph G has a fractional 1-factor if bind(G)≥1and has a fractional k-factor if bind(G)≥k−1k. Furthermore, it is showed that both results are best possible in some sense.
文摘This paper presents learning rates for the least-square regularized regression algorithms with polynomial kernels. The target is the error analysis for the regression problem in learning theory. A regularization scheme is given, which yields sharp learning rates. The rates depend on the dimension of polynomial space and polynomial reproducing kernel Hilbert space measured by covering numbers. Meanwhile, we also establish the direct approximation theorem by Bernstein-Durrmeyer operators in $ L_{\rho _X }^2 $ with Borel probability measure.
基金Supported by the National Natural Science Foundation of China (No. 10771091)Com2MaC-KOSEF (No.(E)ndzr09-15)
文摘In this paper we get some relations between α（G）, α＇（G）, β（G）, β＇（G） and αT（G）, βT（G）. And all bounds in these relations are best possible, where α（G）, α＇（G）,/3（G）, β（G）, αT（G） and βT（G） are the covering number, edge-covering number, independent number, edge-independent number （or matching number）, total covering number and total independent number, respectively.
基金Supported by the National Natural Science Foundation of China (No.10771013 and 10831002)
文摘Abstract A t-hyperwhesl （t 〉 3） of length l （or Wz（t） for brevity） is a t-uniform hypergraph （V, E）, where t E= {e1,e2,...,el} and vl,v2,...,vt are distinct vertices of V = Ui=1 ei such that for i= 1,...,1, vi,vi＋1 ∈ei and ei ∩ ej = P, j ∈ {i - 1, i,i ＋ 1}, where the operation on the subscripts is modulo 1 and P is a vertex of V which is different from vi, 1 〈 i 〈 l. In this paper, the minimum covering problem of MCλ（3, W（3）,v） is investigated. Direct and recursive constructions on MCλ（3, W（3）,v） are presented. The covering number cλ（3, W4（3）, v） is finally determined for any positive integers v 〉 5 and A.
基金Supported by Ningbo Institute of Technology, Zhejiang Univ. Youth Innovation Foundation and Zhejiang Provincial Natural Science Foundation( Y604167).
文摘The relations among the dominating number, independence number and covering number of hypergraphs are investigated. Main results are as follows：Dv（H）≤min{α≤（H）, p（H）, p（H）, T（H）}; De（H）≤min{v（H）, T（H）, p（H）}; DT（H） ≤αT（H）; S（H）≤ Dv （H） ＋ α（H）≤n; 2≤ Dv （H） ＋ T（H） ≤n; 2 〈 Dv （H） ＋ v（H）≤n/2 ＋ [n/r]; Dv （H） ＋ p（H） 〈_n;2≤De（H） ＋ Dv（H）≤n/2 ＋ [n/r];α（H） ＋ De（H）≤n;2 ≤ De（H） ＋ v（H）≤2[n/r]; 2 De（H） ＋ p（H）≤n-r ＋ 2.
基金Supported by 973 Programs(Grant Nos.2013CB834201 and 2011CB302401)the National Science Foundation of China(Grant No.11071003)the Chang Jiang Scholars Program of China
文摘In geometry, there are several challenging problems studying numbers associated to convex bodies. For example, the packing density problem, the kissing number problem, the covering density problem, the packing-covering constant problem, Hadwiger＇s covering conjecture and Borsuk＇s partition conjecture. They are flmdamental and fascinating problems about the same objects. However, up to now, both the methodology and the technique applied to them are essentially different. Therefore, a common foundation for them has been much expected. By treating problems of these types as functionals defined on the spaces of n-dimensional convex bodies, this paper tries to create such a foundation. In particular, supderivatives for these functionals will be studied.
文摘A standard assumption in the literature of learning theory is the samples which are drawn independently from an identical distribution with a uniform bounded output. This excludes the common case with Gaussian distribution. In this paper we extend these assumptions to a general case. To be precise, samples are drawn from a sequence of unbounded and non-identical probability distributions. By drift error analysis and Bennett inequality for the unbounded random variables, we derive a satisfactory learning rate for the ERM algorithm.
基金Supported by the National Natural Science Foundation of China (Grant No. 10871226)
文摘The paper deals with estimates of the covering number for some Mercer kernel Hilbert space with Bernstein-Durrmeyer operators. We first give estimates of l2- norm of Mercer kernel matrices reproducing by the kernelsK（α,β）（x,y）：=∑∞k=0 Ck（α,β）（x）Qk（α,β）（y）,where Qk（α,β） （x） are the Jacobi polynomials of order k on （0, 1 ）, Ck（α,β） 〉 0 are real numbers, and from which give the lower and upper bounds of the covering number for some particular reproducing kernel Hilbert space reproduced by Kα,β （x, y）.
文摘Partially observable Markov decision processes （POMDPs） provide a rich mathematical framework for planning tasks in partially observable stochastic environments. The notion of the covering number, a metric of capturing the search space size of a POMDP planning problem, has been proposed as a complexity measure of approximate POMDP planning. Existing theoretical results are based on POMDPs with finite and discrete state spaces and measured in the l1- metric space. When considering heuristics, they are assumed to be always admissible. This paper extends the theoretical results on the covering numbers of different search spaces, including the newly defined space reachable under inadmissible heuristics, to the ln-metric spaces. We provide a simple but scalable algorithm for estimating covering numbers. Experimentally, we provide estimated covering numbers of the search spaces reachable by following different policies on several benchmark problems, and analyze their abilities to predict the runtime of POMDP planning algorithms.
基金supported by National Natural Science Foundation of China (Grant Nos.11171014 and 11101024)National Basic Research Program of China (973 Project) (Grant No. 2010CB731900)
文摘Semi-supervised learning is an emerging computational paradigm for machine learning,that aims to make better use of large amounts of inexpensive unlabeled data to improve the learning performance.While various methods have been proposed based on different intuitions,the crucial issue of generalization performance is still poorly understood.In this paper,we investigate the convergence property of the Laplacian regularized least squares regression,a semi-supervised learning algorithm based on manifold regularization.Moreover,the improvement of error bounds in terms of the number of labeled and unlabeled data is presented for the first time as far as we know.The convergence rate depends on the approximation property and the capacity of the reproducing kernel Hilbert space measured by covering numbers.Some new techniques are exploited for the analysis since an extra regularizer is introduced.
