Recent years have witnessed a tremendous growth using topological summaries, especially the persistence diagrams (encoding the so-called persistent homology) for analyzing complex shapes. Intuitively, persistent homol...
详细信息
In the 2-Dimensional Knapsack problem (2DK) we are given a square knapsack and a collection of n rectangular items with integer sizes and profits. Our goal is to find the most profitable subset of items that can be pa...
详细信息
In the Demand Strip Packing problem (DSP), we are given a time interval and a collection of tasks, each characterized by a processing time and a demand for a given resource (such as electricity, computational power, e...
详细信息
Approximating the partition function of the ferromagnetic Ising model with general external fields is known to be #BIS-hard in the worst case, even for bounded-degree graphs, and it is widely believed that no polynomi...
详细信息
In this work we investigate the min-max-min robust optimization problem and the kadaptability robust optimization problem for binary problems with uncertain costs. The idea of the first approach is to calculate a set ...
详细信息
In the Priority Steiner Tree (PST) problem, we are given an undirected graph G = (V, E) with a source s ∈ V and terminals T ⊆ V \ {s}, where each terminal v ∈ T requires a nonnegative priority P(v). The goal is to c...
详细信息
We introduce a new two-side approximation method for the channel scheduling problem, which controls the accuracy of approximation in two sides by a pair of parameters (f, g). We present a series of simple and practica...
详细信息
We introduce a new two-side approximation method for the channel scheduling problem, which controls the accuracy of approximation in two sides by a pair of parameters (f, g). We present a series of simple and practical-for-implementation greedy algorithms which give constant factor approximation in both sides. First, we propose four approximation algorithms for the weighted channel allocation problem: 1. a greedy algorithm for the multichannel with fixed interference radius scheduling problem is proposed and an one side O(1)-IS-approximation is obtained;2. a greedy (O(1), O(1))-approximation algorithm for single channel with fixed interference radius scheduling problem is presented;3. we improve the existing algorithm for the multichannel scheduling and show an vertical bar E vertical bar(O(d/epsilon)) time (1 - epsilon)-approximation algorithm;4. we speed up the polynomial time approximation scheme for single-channel scheduling through merging two algorithms and show a (1 - epsilon, O(1))-approximation algorithm. Next, we study two polynomial time constant factor greedy approximation algorithms for the unweighted channel allocation with variate interference radius. A greedy O(1)-approximation algorithm for the multichannel scheduling problem and an (O(1), O(1))-approximation algorithm for single-channel scheduling problem are developed. At last, we do some experiments to verify the effectiveness of our proposed methods.
Given a social network G and an integer k, the influence maximization (IM) problem asks for a seed set S of k nodes from G to maximize the expected number of nodes influenced via a propagation model. The majority of t...
详细信息
Given a social network G and an integer k, the influence maximization (IM) problem asks for a seed set S of k nodes from G to maximize the expected number of nodes influenced via a propagation model. The majority of the existing algorithms for the IM problem are developed only under the non-adaptive setting, i.e., where all k seed nodes are selected in one batch without observing how they influence other users in real world. In this paper, we study the adaptive IM problem where the k seed nodes are selected in batches of equal size b, such that the i-th batch is identified after the actual influence results of the former i-1 batches are observed. In this paper, we propose the first practical algorithm for the adaptive IM problem that could provide the worst-case approximation guarantee of 1 - e(rho b(epsilon-1)), where rho(b)=1-(1-1/b)(b) and epsilon is an element of(0,1) is a user-specified parameter. In particular, we propose a general framework AdaptGreedy that could be instantiated by any existing non-adaptive IM algorithms with expected approximation guarantee. Our approach is based on a novel randomized policy that is applicable to the general adaptive stochastic maximization problem, which may be of independent interest. In addition, we propose a novel non-adaptive IM algorithm called EPIC which not only provides strong expected approximation guarantee, but also presents superior performance compared with the existing IM algorithms. Meanwhile, we clarify some existing misunderstandings in recent work and shed light on further study of the adaptive IM problem. We conduct experiments on real social networks to evaluate our proposed algorithms comprehensively, and the experimental results strongly corroborate the superiorities and effectiveness of our approach.
We consider a transmission scheduling problem in which multiple agents receive update information through a shared Time Division Multiple Access (TDMA) channel. To provide timely delivery of update information, the pr...
详细信息
We consider a transmission scheduling problem in which multiple agents receive update information through a shared Time Division Multiple Access (TDMA) channel. To provide timely delivery of update information, the problem asks for a schedule that minimizes the overall Age of Information (AoI). We call this problem the Min-AoI problem. Several special cases of the problem are known to be solvable in polynomial time. Our contribution is threefold. First, we introduce a new job scheduling problem called the Min-WCS problem, and we prove that, for any constant r >= 1, every r-approximation algorithm for the Min-WCS problem can be transformed into an r-approximation algorithm for the Min-AoI problem. Second, we give a randomized 2.619-approximation algorithm, a randomized 3-approximation algorithm, which outperforms the previous one in certain scenarios, and a dynamic-programming-based exact algorithm for the Min-WCS problem. Finally, we prove that the Min-AoI problem is NP-hard.
In the Two-Bar Charts Packing Problem (2-BCPP), it is required to pack the bar charts (BCs) consisting of two bars into the horizontal unit-height strip of minimal length. The bars may move vertically within the strip...
详细信息
暂无评论