We investigate two NP-complete vertex partition problems on edge-weighted complete graphs with 3k vertices. The first problem asks to partition the graph into k vertex disjoint paths of length 2 (referred to as 2-path...
详细信息
We investigate two NP-complete vertex partition problems on edge-weighted complete graphs with 3k vertices. The first problem asks to partition the graph into k vertex disjoint paths of length 2 (referred to as 2-paths) such that the total weight of the paths is maximized. We present a cubic time approximation algorithm that computes a 2-path partition whose total weight is at least .5833 of the weight of an optimal partition, improving upon the (.5265 - is an element of)-approximation algorithm of Tanahashi and Chen (2010). Restricting the input to graphs with edge weights in {0, 1), we present a .75 approximation algorithm improving upon the .55-approximation algorithm of Hassin and Schneider (2013). Combining this algorithm with a previously known approximation algorithm for the 3-SET PACKING problem, we obtain a .6-approximation algorithm for the problem of partitioning a {0, 1)-edge-weighted graph into k vertex disjoint triangles of maximum total weight. The best known approximation algorithm for general weights is due to Chen and Tanahashi (2009) and achieves an approximation ratio of .5257. (C) 2018 Elsevier B.V. All rights reserved.
We study the PRIZE-COLLECTING STEINER TREE (PCST), PRIZE-COLLECTING TRAVELING SALESMAN (PCTSP), and PRIZE-COLLECTING PATH (PC-PATH) problems. Given a graph (V, E) with a cost on each edge and a penalty (a.k.a. prize) ...
详细信息
We study the PRIZE-COLLECTING STEINER TREE (PCST), PRIZE-COLLECTING TRAVELING SALESMAN (PCTSP), and PRIZE-COLLECTING PATH (PC-PATH) problems. Given a graph (V, E) with a cost on each edge and a penalty (a.k.a. prize) on each node, the goal is to find a tree (for PCST), cycle (for PCTSP), or path (for PC-PATH) that minimizes the sum of the edge costs in the tree/cycle/path and the penalties of the nodes not spanned by it. In addition to being a useful theoretical tool for helping to solve other optimization problems, PCST has been applied fruitfully by AT&T to the optimization of real-world telecommunications networks. The most recent improvements for the first two problems, a 2-approximation algorithm for each, appeared first in 1992;a 2-approximation for PC-PATH appeared in 2003. The natural linear programming relaxation of PCST has an integrality gap of 2, which has been a barrier to further improvements for this problem. We present (2-epsilon)-approximation algorithms for all three problems, connected by a unified technique for improving prize-collecting algorithms that allows us to circumvent the integrality gap barrier. Specifically, our approximation ratio for PRIZE-COLLECTING STEINER TREE is below 1.9672.
The local ratio technique is a methodology for the design and analysis of algorithms for a broad range of optimization problems. The technique is remarkably simple and elegant, and yet can be applied to several classi...
详细信息
The local ratio technique is a methodology for the design and analysis of algorithms for a broad range of optimization problems. The technique is remarkably simple and elegant, and yet can be applied to several classical and fundamental problems (including covering problems, packing problems, and scheduling problems). The local ratio technique uses elementary math and requires combinatorial insight into the structure and properties of the problem at hand. Typically, when using the technique, one has to invent a weight function for a problem instance under which every "reasonable" solution is "good." The local ratio technique is closely related to the primal-dual schema, though it is not based on weak LP duality (which is the basis of the primal-dual approach) since it is not based on linear programming. In this survey we, introduce the local ratio technique and demonstrate its use in the design and analysis of algorithms for various problems. We trace the evolution path of the technique since its inception in the 1980's, culminating with the most recent development, namely, fractional local ratio, which can be viewed as a new LP rounding technique.
We consider two-and multistage versions of stochastic combinatorial optimization problems with recourse: in this framework, the instance for the combinatorial optimization problem is drawn from a known probability dis...
详细信息
We consider two-and multistage versions of stochastic combinatorial optimization problems with recourse: in this framework, the instance for the combinatorial optimization problem is drawn from a known probability distribution p and is only revealed to the algorithm over two (or multiple) stages. At each stage, on receiving some more information about the instance, the algorithm is allowed to build some partial solution. Since the costs of elements increase with each passing stage, there is a natural tension between waiting for later stages, to gain more information about the instance, and purchasing elements in earlier stages, to take advantages of lower costs. We provide approximation algorithms for stochastic combinatorial optimization problems (such as the Steiner tree problem, the Steiner network problem, and the vertex cover problem) by means of a simple sampling-based algorithm. In every stage, our algorithm samples the probability distribution of the requirements and constructs a partial solution to serve the resulting sample. We show that if one can construct cost-sharing functions associated with the algorithms used to construct these partial solutions, then this strategy results in provable approximation guarantees for the overall stochastic optimization problem. We also extend this approach to provide an approximation algorithm for the stochastic version of the uncapacitated facility location problem, a problem that does not fit into the simpler framework of our main model.
Various recent theoretical studies have achieved considerable progress in understanding combined link scheduling and power control in wireless networks with SINR constraints. These analyses were mainly focused on desi...
详细信息
Various recent theoretical studies have achieved considerable progress in understanding combined link scheduling and power control in wireless networks with SINR constraints. These analyses were mainly focused on designing and analyzing approximation algorithms with provable approximation guarantees. While these studies revealed interesting effects from a theoretical perspective, so far there has not been a systematic evaluation of the theoretical results in simulations. In this paper, we examine the performance of various approximation algorithms and heuristics for the common scheduling problems on instances generated by different random network models, e.g., taking clustering effects into account. Using (mixed) integer linear programming, we are able to compute the theoretical optima for some of these instances such that the performance of the different algorithms can be compared with these optima. The simulations support the practical relevance of the theoretical findings. For example, setting transmission powers by a square-root power assignment, the network's capacity increases significantly in comparison to uniform power assignments. Furthermore, the developed approximation algorithms are able to exploit this gap providing in general a better performance than any algorithm using uniform transmission powers, even with unlimited computational power. The obtained results are robust against changes in parameters and network generation models. (C) 2014 Elsevier B.V. All rights reserved.
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 the polynomial time approximation of the NP-hard MAX k-VERTEX COVER problem in bipartite graphs and propose purely combinatorial approximation algorithms . The main result of the paper is a simple combinatori...
详细信息
We study the polynomial time approximation of the NP-hard MAX k-VERTEX COVER problem in bipartite graphs and propose purely combinatorial approximation algorithms . The main result of the paper is a simple combinatorial algorithm and a computer-assisted analysis of its approximation guarantee giving strong evidence that the worst approximation ratio achieved is bounded below by 0.821. We also study two simpler strategies with provable approximation ratios of 2/3 and 34/47 approximate to 0.72 respectively that already beat the only such known algorithm, namely the greedy approach which guarantees ratio (1-1/e) approximate to 0.632. Our principal motivation is to bring a satisfactory answer in the following question: to what extent combinatorial methods for MAX k-VERTEX COVEr compete with linear programming ones? (C) 2017 Elsevier B.V. All rights reserved.
A stochastic approximation procedure that minimizes a mean-square-error criterion is proposed in this paper. It is applied first to derive an algorithm for recursive estimation of the mean-square-error approximation o...
详细信息
A stochastic approximation procedure that minimizes a mean-square-error criterion is proposed in this paper. It is applied first to derive an algorithm for recursive estimation of the mean-square-error approximation of the function which relates the input signals and the responses of a memoryless system. The input signals are assumed to be generated at random with an unknown probability density function, and the response is measured with an error which has zero mean and finite variance. A performance index for evaluating the rate of convergence of the algorithm is defined and then the optimal form of the algorithm is derived. It is shown that the least-square-error fit of the measured output signals of the systems offers a recursive formula which is a special case of the proposed algorithm. A recursive formula for estimation of a priori probabilities of the pattern classes using unclassified samples is then presented. The rate of convergence is computed. A minimum square-error estimate of a continuous probability density function is also obtained by the same algorithm.
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.
暂无评论