Given an edge-weighted complete graph G on 3n vertices, the maximum-weight triangle packing problem asks for a collection of n vertex-disjoint triangles in G such that the total weight of edges in these n triangles is...
详细信息
Given an edge-weighted complete graph G on 3n vertices, the maximum-weight triangle packing problem asks for a collection of n vertex-disjoint triangles in G such that the total weight of edges in these n triangles is maximized. Although the problem has been extensively studied in the literature, it is surprising that prior to this work, no nontrivial approximation algorithm had been designed and analyzed for its metric case, where the edge weights in the input graph satisfy the triangle inequality. In this paper, we design the first nontrivial polynomial-time approximation algorithm for the maximum-weight metric triangle packing problem. Our algorithm is randomized and achieves an expected approximation ratio of 0.66768 - epsilon for any constant epsilon > 0.
In this paper, we study the generalized submodular maximization problem with a nonnegative monotone submodular set function as the objective function and subject to a matroid constraint. The problem is generalized thr...
详细信息
In this paper, we study the generalized submodular maximization problem with a nonnegative monotone submodular set function as the objective function and subject to a matroid constraint. The problem is generalized through the curvature parameter alpha is an element of [0, 1] which measures how far a set function deviates from linearity to submodularity. We propose a deterministic approximation algorithm which uses the approximation algorithm proposed by Buchbinder et al. [2] as a building block and inherits the approximation guarantee for alpha = 1. For general value of the curvature parameter alpha is an element of [0, 1], we present an approximation algorithm with a factor of 1+h(alpha)(y)+Delta.[3+alpha-(2+alpha)y-(1+alpha)h(alpha)(y)]/2+alpha+(1+alpha)(1-y), where y is an element of [0, 1] is a predefined parameter for tuning the ratio. In particular, when alpha = 1 we obtain a ratio 0.5008 when setting y = 0.9, coinciding with the renowned state-of-art approximate ratio; when alpha = 0 that the object is a linear function, the approximation factor equals one and our algorithm is indeed an exact algorithm that always produces optimum solutions. (C) 2021 Elsevier B.V. All rights reserved.
We devise a constant-factor approximation algorithm for the maximization version of the edge-disjoint paths problem if the supply graph together with the demand edges forms a planar graph. By planar duality, this is e...
详细信息
We devise a constant-factor approximation algorithm for the maximization version of the edge-disjoint paths problem if the supply graph together with the demand edges forms a planar graph. By planar duality, this is equivalent to packing cuts in a planar graph such that each cut contains exactly one demand edge. We also show that the natural linear programming relaxations have constant integrality gap, yielding an approximate max-multiflow min-multicut theorem.
Cloud providers face the challenge of efficiently managing their infrastructure through minimizing resource consumption while allocating service requests such that their revenue is maximized. Solutions addressing this...
详细信息
Cloud providers face the challenge of efficiently managing their infrastructure through minimizing resource consumption while allocating service requests such that their revenue is maximized. Solutions addressing this challenge should consider the sharing of memory pages among virtual machines (VMs) and the available capacity of each type of requested resources. We provide such solution by designing a greedy approximation algorithm for solving the sharing-aware virtual machine revenue maximization (SAVMRM) problem. The SAVMRM problem requires determining the set of VMs that can be instantiated on a given server such that the revenue derived from hosting the VMs is maximized. In addition, we model the SAVMRM problem as a multilinear binary program and optimally solve it, while accounting for page sharing and multiple resource constraints. We determine and analyze the approximability properties of our proposed greedy algorithm and evaluate it by performing extensive experiments using Google cluster workload traces. The experimental results show that under various scenarios, our proposed algorithm generates higher revenue than other VM allocation algorithms while achieving significant reduction of allocated memory.
The optimal path to be followed by an automatic cutter to cut a set of shapes arranged on a material is termed as the cutting path determination problem. The shapes are often considered as polygons. Each polygon can b...
详细信息
The optimal path to be followed by an automatic cutter to cut a set of shapes arranged on a material is termed as the cutting path determination problem. The shapes are often considered as polygons. Each polygon can be either cut entirely (complete cutting approach) or partially (partial cutting approach) before cutting the next polygon. This work solves the cutting path determination problem using the partial cutting approach. The proposed approximation algorithm uses the concepts of ma tching, s panning tree, and tri angulation, and is hence termed as MASTRI. The MASTRI algorithm has a time complexity of O(n logn) where n is the total number of vertices of all the polygons. The cutting path computed by the MASTRI algorithm is guaranteed to be within a factor of 3/2 of optimum travel distance of the cutter. No other algorithm has been developed for the partial cutting approach which runs in polynomial time. The MASTRI algorithm is evaluated on 285 input problems, of which 192 problems are randomly generated, and 93 problems are taken from literature. The experimental analysis shows that the MASTRI algorithm computes the cutting path in a very short amount of time. The comparison of MASTRI algorithm with existing works in the literature shows that the MASTRI algorithm gives a shorter cutting path in less time. The MASTRI algorithm can be used for computing cutting path in industries like sheet metal cutting.
In this letter, we study the optimum selection of ground stations (GSs) in RF/optical satellite networks (SatNets) in order to minimize the overall installation cost under an outage probability requirement, assuming i...
详细信息
In this letter, we study the optimum selection of ground stations (GSs) in RF/optical satellite networks (SatNets) in order to minimize the overall installation cost under an outage probability requirement, assuming independent weather conditions between sites. First, we show that the optimization problem can be formulated as a binary-linear-programming problem, and then we give a formal proof of its NP-hardness. Furthermore, we design a dynamic-programming algorithm of pseudo-polynomial complexity with global optimization guarantee as well as an efficient (polynomial-time) approximation algorithm with provable performance guarantee on the distance of the achieved objective value from the global optimum. Finally, the performance of the proposed algorithms is verified through numerical simulations.
A multidepot capacitated vehicle routing problem aims to serve customers' demands using a fleet of capacitated vehicles located in multiple depots, such that the total travel cost of the vehicles is minimized. We ...
详细信息
A multidepot capacitated vehicle routing problem aims to serve customers' demands using a fleet of capacitated vehicles located in multiple depots, such that the total travel cost of the vehicles is minimized. We study a variant of this problem, the k-depot split delivery vehicle routing problem (or k-DSDVRP in short), for the situation where each customer's demand can be served by more than one vehicle, and the total number of depots, denoted by k >= 2, is a fixed constant. This is a challenging problem with broad applications in the logistics industry, for which no constant ratio approximation algorithm is known. We develop a new approximation algorithm for the k-DSDVRP, ensuring an approximation ratio of (6 4/k) and a polynomial running time for any fixed constant k >= 2. To achieve this, we propose a novel solution framework based on a new relaxation of the problem, a cycle splitting procedure, and a vehicle assignment procedure. To further enhance its efficiency for practical usage, we adapt the newly developed approximation algorithm to a heuristic, which runs in polynomial time even when k is arbitrarily large. Experimental results show that this heuristic outperforms a commercial optimization solver and a standard vehicle routing heuristic. Moreover, our newly proposed solution framework can be applied to developing new constant ratio approximation algorithms for several other variants of the k-DSDVRP with k >= 2 a fixed constant.
The lower-bounded k-median problem plays a key role in many applications related to privacy protection, which requires that the amount of assigned client to each facility should not be less than the requirement. Unfor...
详细信息
The lower-bounded k-median problem plays a key role in many applications related to privacy protection, which requires that the amount of assigned client to each facility should not be less than the requirement. Unfortunately, the lower-bounded clustering problem remains elusive under the widely studied k-median objective. Within this paper, we convert this problem to the capacitated facility location problem and successfully give a(516+ε)-approximation for this problem.
In the edge-cloud environment, offloading technique decides the task to be executed either at the cloud or at the edge. Offloading can improve the quality of service and the efficiency of the system. In most previous ...
详细信息
ISBN:
(纸本)9783030590161;9783030590154
In the edge-cloud environment, offloading technique decides the task to be executed either at the cloud or at the edge. Offloading can improve the quality of service and the efficiency of the system. In most previous works on the offloading problem, the communication costs between tasks on both cloud side or the edge side are often ignored. We consider a general offloading model where the communication costs between any two tasks is non-zero and asymmetric. Moreover, due to the resource limitation on the edge side, we assume that the number of tasks executed on the edge side is bounded by a fixed constant k. This generalized offloading problem is NP-hard in minimizing the total cost with cardinality constraint. Based on semidefinite program, we give an approximation algorithm with the performance guarantee of 2/pi.
We give the first 2-approximation algorithm for the cluster vertex deletion problem. This is tight, since approximating the problem within any constant factor smaller than 2 is UGC-hard. Our algorithm combines the pre...
详细信息
ISBN:
(纸本)9783030738792;9783030738785
We give the first 2-approximation algorithm for the cluster vertex deletion problem. This is tight, since approximating the problem within any constant factor smaller than 2 is UGC-hard. Our algorithm combines the previous approaches, based on the local ratio technique and the management of true twins, with a novel construction of a "good" cost function on the vertices at distance at most 2 from any vertex of the input graph. As an additional contribution, we also study cluster vertex deletion from the polyhedral perspective, where we prove almost matching upper and lower bounds on how well linear programming relaxations can approximate the problem.
暂无评论