The first moment and second central moments of the portfolio return, a.k.a. mean and variance, have been widely employed to assess the expected profit and risk of the portfolio. Investors pursue higher mean and lower ...
详细信息
The first moment and second central moments of the portfolio return, a.k.a. mean and variance, have been widely employed to assess the expected profit and risk of the portfolio. Investors pursue higher mean and lower variance when designing the portfolios. The two moments can well describe the distribution of the portfolio return when it follows the Gaussian distribution. However, the real world distribution of assets return is usually asymmetric and heavy-tailed, which is far from being a Gaussian distribution. The asymmetry and the heavy-tailedness are characterized by the third and fourth central moments, i.e., skewness and kurtosis, respectively. Higher skewness and lower kurtosis are preferred to reduce the probability of extreme losses. However, incorporating high-order moments in the portfolio design is very difficult due to their non-convexity and rapidly increasing computational cost with the dimension. In this paper, we propose a very efficient and convergence-provable algorithm framework based on the successive convex approximation (SCA) algorithm to solve high-order portfolios. The efficiency of the proposed algorithm framework is demonstrated by the numerical experiments.
We study a revenue maximization problem in the context of social networks. Namely, we generalize a model introduced by Alon, Mansour, and Tennenholtz [2] that captures inequity aversion, i.e., it captures the fact tha...
详细信息
We study a revenue maximization problem in the context of social networks. Namely, we generalize a model introduced by Alon, Mansour, and Tennenholtz [2] that captures inequity aversion, i.e., it captures the fact that prices offered to neighboring nodes should not differ significantly. We first provide approximation algorithms for a natural class of instances, where the total revenue is the sum of single-value revenue functions. Our results improve on the current state of the art, especially when the number of distinct prices is small. This applies, for instance, to settings where the seller will only consider a fixed number of discount types or special offers. To complement our positive results, we resolve one of the open questions posed in [2] by establishing APX-hardness for the problem. Surprisingly, we further show that the problem is NP-complete even when the price differences are allowed to be large, or even when the number of allowed distinct prices is as small as three. Finally, we study extensions of the model regarding the demand type of the clients. (C) 2021 Elsevier B.V. All rights reserved.
In this paper we present approximation algorithm for the following NP-hard map labeling problem: Given a set S of n distinct sites in the plane, one needs to place at each site a uniform square of maximum possible siz...
详细信息
In this paper we present approximation algorithm for the following NP-hard map labeling problem: Given a set S of n distinct sites in the plane, one needs to place at each site a uniform square of maximum possible size such that all the squares are along the same direction. This generalizes the classical problem of labeling points with axis-parallel squares and restricts the most general version where the squares can have different orientations. We obtain factor-4 and factor-5 root2 approximation algorithms for this problem. These algorithms also work for two generalized versions of the problem. We also revisit the problem of labeling each point with maximum uniform axis-parallel square pairs and improve the previous approximation factor of 4 to 3.
In this paper we deal with two geometric problems arising from heterogeneous parallel computing: how to partition the unit square into p rectangles of given areas s(1), s(2), ... s(p) (such that Sigma(i=l)(p) s(i) = l...
详细信息
In this paper we deal with two geometric problems arising from heterogeneous parallel computing: how to partition the unit square into p rectangles of given areas s(1), s(2), ... s(p) (such that Sigma(i=l)(p) s(i) = l),so as to minimize either (i) the sum of the p perimeters of the rectangles or (ii) the largest perimeter of the p rectangles? For both problems, we prove NP-completeness and we introduce a 7/4-approximation algorithm for (i) and a 4 (2/root3)-approximation algorithm for (ii).
We construct new approximation algorithms for MAX SET SPLITTING and MAX NOT-ALL-EQUAL SAT which when combined with existing algorithms give the best approximation results so far for these problems. Furthermore, we sol...
详细信息
We construct new approximation algorithms for MAX SET SPLITTING and MAX NOT-ALL-EQUAL SAT which when combined with existing algorithms give the best approximation results so far for these problems. Furthermore, we solve a linear program to find an upper bound on the performance ratio. This linear program can also be used to see which of the contributing algorithms it is possible to exclude from the combined algorithm without affecting its performance ratio. (C) 1998 Elsevier Science B.V.
In this paper, we give randomized approximation algorithms for stochastic cumulative VRPs for the split and unsplit deliveries. The approximation ratios are max{1 + 1.5 alpha, 3} and 6, respectively, where a is the ap...
详细信息
In this paper, we give randomized approximation algorithms for stochastic cumulative VRPs for the split and unsplit deliveries. The approximation ratios are max{1 + 1.5 alpha, 3} and 6, respectively, where a is the approximation ratio for the metric TSP. The approximation factor is further reduced for trees. These results extend the results in Anupam Gupta et al. (2012) and Daya Ram Gaur et al. (2013). The bounds reported here improve the bounds in Daya Ram Gaur et al. (2016). (C) 2018 Elsevier B.V. All rights reserved.
In this paper, we present a new bicriteria approximation algorithm for the degree-bounded minimum spanning tree problem. I this problem, we are given an undirected graph, a nonnegative cost function on the edges, and ...
详细信息
In this paper, we present a new bicriteria approximation algorithm for the degree-bounded minimum spanning tree problem. I this problem, we are given an undirected graph, a nonnegative cost function on the edges, and a positive integer B, and the goal is to find a minimum-cost spanning tree T with maximum degree at most B*. In an n-node graph, our algorithm finds a spanning tree with maximum degree O (B* + log n) and cost O (opt B*), where opt B* is the minimum cost of any spanning tree whose maximum degree is at most B* Our algorithm uses ideas from Lagrangean duality. We show how a set of optimum Lagrangean multipliers yields bounds on both the degree and the cost of the computed solution.
Efficient construction of large-scale linkage maps is highly desired in current gene mapping projects. To evaluate the performance of available approaches in the literature, four published methods, the insertion (IN),...
详细信息
Efficient construction of large-scale linkage maps is highly desired in current gene mapping projects. To evaluate the performance of available approaches in the literature, four published methods, the insertion (IN), seriation (SER), neighbor mapping (NM), and unidirectional growth (UG) were compared on the basis of simulated F(2) data with various population sizes, interferences, missing genotype rates, and mis-genotyping rates. Simulation results showed that the IN method outperformed, or at least was comparable to, the other three methods. These algorithms were also applied to a real data set and results showed that the linkage order obtained by the IN algorithm was superior to the other methods. Thus, this study suggests that the IN method should be used when constructing large-scale linkage maps.
作者：
Fujii, KaitoKyoto Univ
Grad Sch Informat Sakyo Ku 36-1 Yoshida Honmachi Kyoto 6068501 Japan
Maximizing a monotone submodular function subject to a b-matching constraint is increasing in importance due to its application to the content spread maximization problem, but few practical algorithms are known other ...
详细信息
Maximizing a monotone submodular function subject to a b-matching constraint is increasing in importance due to its application to the content spread maximization problem, but few practical algorithms are known other than the greedy algorithm. The best approximation scheme so far is the local search algorithm, proposed by Feldman, Naor, Schwartz, and Ward [8] (2011). It obtains a 1/(2 + 1/k + is an element of)-approximate solution for an arbitrary positive integer k and positive real number is an element of. For graphs with n vertices and m edges, the running time of the local search algorithm is O(b(k+1) (Delta - 1)(k)nm is an element of(-1)) where Delta is the maximum degree, which is impractical for large problems. In this paper, we present two new algorithms for this problem. One is a find walk algorithm that runs in O(bm) time and achieves 1/4-approximation. It is faster than the greedy algorithm whose approximation ratio is 1/3. The other one is a randomized local search algorithm that is a faster variant of the local search algorithm. In expectation, it runs in O(b(k+1) (Delta - 1)(k-1)m log 1/is an element of) time and obtains a (1/(2 + 1/k) - is an element of)-approximate solution. (C) 2016 Elsevier B.V. All rights reserved.
The projection games (aka Label Cover) problem is of great importance to the field of approximation algorithms, since most of the NP-hardness of approximation results we know today are reductions from Label Cover. In ...
详细信息
The projection games (aka Label Cover) problem is of great importance to the field of approximation algorithms, since most of the NP-hardness of approximation results we know today are reductions from Label Cover. In this paper we design several approximation algorithms for projection games: (1) A polynomial-time approximation algorithm that improves on the previous best approximation by Charikar et al. (Algorithmica 61(1):190-206, 2011). (2) A sub-exponential time algorithm with much tighter approximation for the case of smooth projection games. (3) A polynomial-time approximation scheme (PTAS) for projection games on planar graphs and a tight running time lower bound for such approximation schemes. The conference version of this paper had only the PTAS but not the running time lower bound.
暂无评论