A k -submodular function takes k distinct, non-overlapping subsets of a ground set as input and outputs a value. It is a generalization of the well-known submodular function, which is the case when k = 1 and takes a single subset as input. We study the problem of maximizing a non-negative k -submodular function under a knapsack constraint. Greedy+Singleton is an algorithm that chooses the better solution between the fully greedy solution and the best single-element solution, with query complexity and running time of O ( n 2 k ) . We show that Greedy+Singleton has an approximation ratio of 0.273 for monotone functions , which improves the previous analysis of 0.158 in the literature. Moreover, we give the first analysis of Greedy+Singleton for non-monotone k -submodular functions, and prove an approximation ratio of 0.219.

A k-submodular function is a generalization of submodular functions that takes k disjoint subsets as input and outputs a real value. It captures many problems in combinatorial optimization and machine leaning such as influence maximization, sensor placement, feature selection, etc. In this paper, we consider the monotone k-submodular maximization problem under a knapsack constraint, and explore the performance guarantee of a greedy-based algorithm: enumerating all size-2 solutions and extending every singleton solution greedily; the best outcome is returned. We provide a novel analysis framework and prove that this algorithm achieves an approximation ratio of at least 0.328. This is the best-known result of combinatorial algorithms on k-submodular knapsack maximization. In addition, within the framework, we can further improve the approximation ratio to a value approaching 1/3 with any desirable accuracy, by enumerating sufficiently large base solutions. The results can even be extended to non-monotone k-submodular functions.

High spatial correlation is one of the main factors limiting the communication performance of multiple-input multiple-output (MIMO) visible light communication (VLC), which can be alleviate by precoding. However, most existing precoding algorithms require a dedicated baseband chain for each light emitting diode (LED), which may result in high energy consumption and hardware complexity, especially when LEDs are densely deployed. To solve this issue, a successive interference cancellation-based precoding scheme with sub-connected architecture (SIC-SA) is proposed, where each baseband chain is connected to an LED sub-array. In this case, since the SIC-based precoding can only determine the signal of each baseband chain for an LED sub-array, the electrical/optical power of each LED must be jointly optimized to alleviate the spatial correlation among individual LEDs. This joint SIC-based precoding, power allocation and direct current offset design problem is formulated as an achievable sum rate maximization problem under dimming control and electrical power constraints. To solve this problem, the original problem is separated into two subproblems. In the first subproblem, the SIC-based precoding is calculated by successive null space computation. With the obtained SIC-based precoding, the second subproblem optimizes the power allocation and direct-current offset. Finally, these two subproblems are iteratively solved to obtain a convergent solution. Simulation results demonstrate that the proposed SIC-SA achieves 0.1306 bps/Hz/W and 0.1340 bps/Hz/W improvements in terms of energy efficiency compared to minimum mean square error precoding with fully-connected architecture (FA) and zero-forcing precoding with FA, respectively, when the signal-to-noise ratio is 30 dB.

Network embedding assigns nodes in a network to low-dimensional representations and effectively preserves the structure and inherent properties of the network. Most existing network embedding methods didn't consider network noise. However, it is almost impossible to observe the actual structure of a real-world network without noise. The noise in the network will affect the performance of network embedding dramatically. In this paper, we aim to exploit node similarity to address the problem of social network embedding with noise and propose a node similarity preserving (NSP) embedding method. NSP exploits a comprehensive similarity index to quantify the authenticity of the observed network structure. Then we propose an algorithm to construct a correction matrix to reduce the influence of noise. Finally, an objective function for accurate network embedding is proposed and an efficient algorithm to solve the optimization problem is provided. Extensive experimental results on a variety of applications of real-world networks with noise show the superior performance of the proposed method over the state-of-the-art methods.