二分图受约束最小点覆盖问题作为一个NP-完全问题,无法在多项式时间内得到最优解,除非P=NP。基于此,本文提出了一种基于链暗示技术的二分图受约束最小点覆盖问题的近似算法,具体为:当二分图受约束最小点覆盖问题实例中存在满足约束条件...二分图受约束最小点覆盖问题作为一个NP-完全问题,无法在多项式时间内得到最优解,除非P=NP。基于此,本文提出了一种基于链暗示技术的二分图受约束最小点覆盖问题的近似算法,具体为:当二分图受约束最小点覆盖问题实例中存在满足约束条件的最小点覆盖(ku,kl)时,对任意给定的近似率δ=1+ε>1,一定可以找到一个受约束近似点覆盖(ku,kl),对应的近似率为max{ku/ku,kl/kl}≤1+ε,整个近似算法的运行时间复杂度为O(22/ε)。显然,它是二分图受约束最小点覆盖问题的一个多项式时间近似方案(polynomial time approximation scheme,PTAS算法)。展开更多
We propose a novel method to compute globally injective parameterizations with arbitrary positional constraints on disk topology meshes.Central to this method is the use of a scaffold mesh that reduces the globally in...We propose a novel method to compute globally injective parameterizations with arbitrary positional constraints on disk topology meshes.Central to this method is the use of a scaffold mesh that reduces the globally injective constraint to a locally flipfree condition.Hence,given an initial parameterized mesh containing flipped triangles and satisfying the positional constraints,we only need to remove the flips of a overall mesh consisting of the parameterized mesh and the scaffold mesh while always meeting positional constraints.To successfully apply this idea,we develop two key techniques.Firstly,an initialization method is used to generate a valid scaffold mesh and mitigate difficulties in eliminating flips.Secondly,edgebased remeshing is used to optimize the regularity of the scaffold mesh containing flips,thereby improving practical robustness.Compared to state-of-the-art methods,our method is much more robust.We demonstrate the capability and feasibility of our method on a large number of complex meshes.展开更多
It iswell known that traditionalmean-variance optimal portfolio delivers rather erratic and unsatisfactory out-of-sample performance due to the neglect of estimation errors.Constrained solutions,such as no-short-sale-...It iswell known that traditionalmean-variance optimal portfolio delivers rather erratic and unsatisfactory out-of-sample performance due to the neglect of estimation errors.Constrained solutions,such as no-short-sale-constrained and norm-constrained portfolios,can usually achieve much higher ex post Sharpe ratio.Bayesian methods have also been shown to be superior to traditional plug-in estimator by incorporating parameter uncertainty through prior distributions.In this paper,we develop an innovative method that induces priors directly on optimal portfolio weights and imposing constraints a priori in our hierarchical Bayes model.We showthat such constructed portfolios are well diversified with superior out-of-sample performance.Our proposed model is tested on a number of Fama–French industry portfolios against the na飗e diversification strategy and Chevrier and McCulloch’s(2008)economically motivated prior(EMP)strategy.On average,our model outperforms Chevrier and McCulloch’s(2008)EMP strategy by over 15%and outperform the‘1/N’strategy by over 50%.展开更多
文摘二分图受约束最小点覆盖问题作为一个NP-完全问题,无法在多项式时间内得到最优解,除非P=NP。基于此,本文提出了一种基于链暗示技术的二分图受约束最小点覆盖问题的近似算法,具体为:当二分图受约束最小点覆盖问题实例中存在满足约束条件的最小点覆盖(ku,kl)时,对任意给定的近似率δ=1+ε>1,一定可以找到一个受约束近似点覆盖(ku,kl),对应的近似率为max{ku/ku,kl/kl}≤1+ε,整个近似算法的运行时间复杂度为O(22/ε)。显然,它是二分图受约束最小点覆盖问题的一个多项式时间近似方案(polynomial time approximation scheme,PTAS算法)。
基金supported by the National Natural Science Foundation of China(61802359,62025207)USTC Research Funds of the Double First-Class Initiative(YD0010002003).
文摘We propose a novel method to compute globally injective parameterizations with arbitrary positional constraints on disk topology meshes.Central to this method is the use of a scaffold mesh that reduces the globally injective constraint to a locally flipfree condition.Hence,given an initial parameterized mesh containing flipped triangles and satisfying the positional constraints,we only need to remove the flips of a overall mesh consisting of the parameterized mesh and the scaffold mesh while always meeting positional constraints.To successfully apply this idea,we develop two key techniques.Firstly,an initialization method is used to generate a valid scaffold mesh and mitigate difficulties in eliminating flips.Secondly,edgebased remeshing is used to optimize the regularity of the scaffold mesh containing flips,thereby improving practical robustness.Compared to state-of-the-art methods,our method is much more robust.We demonstrate the capability and feasibility of our method on a large number of complex meshes.
基金This work was supported in part by US National Science Foundation(NSF)under grant DMS-1613110。
文摘It iswell known that traditionalmean-variance optimal portfolio delivers rather erratic and unsatisfactory out-of-sample performance due to the neglect of estimation errors.Constrained solutions,such as no-short-sale-constrained and norm-constrained portfolios,can usually achieve much higher ex post Sharpe ratio.Bayesian methods have also been shown to be superior to traditional plug-in estimator by incorporating parameter uncertainty through prior distributions.In this paper,we develop an innovative method that induces priors directly on optimal portfolio weights and imposing constraints a priori in our hierarchical Bayes model.We showthat such constructed portfolios are well diversified with superior out-of-sample performance.Our proposed model is tested on a number of Fama–French industry portfolios against the na飗e diversification strategy and Chevrier and McCulloch’s(2008)economically motivated prior(EMP)strategy.On average,our model outperforms Chevrier and McCulloch’s(2008)EMP strategy by over 15%and outperform the‘1/N’strategy by over 50%.
