Finding dense subgraphs from a large graph is a fundamental graph mining task with many applications. The notion is recently formulated of locally densest subgraph (LDS) is recently formulated to identify multiple dense subgraphs that cover different regions of a large graph. Informally, an LDS is a subgraph with the highest density in its local region. The state-of-the-art algorithm for computing top-k LDSes with the highest densities is LDS. It iteratively computes the densest subgraph and removes it from the graph, where all the computed densest subgraphs form the candidates of LDSes. Then, each candidate is verified through a costly maximum flow computation. Although advanced pruning techniques are proposed in LDS, the verification step is still time consuming especially for not-so-small k values. In this paper, we aim to improve the efficiency of finding top-k LDSes by designing verification-free approaches. Our algorithms are based on our observation that the set of maximal λ-compact subgraphs for all possible λ values form a hierarchical structure, and LDSes are simply leaves in the hierarchical structure. Thus, we propose a divide-and-conquer algorithm LDS-DC as well as an optimized algorithm LDS-Opt to efficiently identify top-k LDSes without constructing the entire hierarchical structure. Both of our algorithms have lower time complexities than LDS. Extensive empirical studies on real graphs show that our optimized algorithm LDS-Opt outperforms LDS for all k values, and the improvement is up-to several orders of magnitude.

While generative models achieve remarkable success in recent years, applying them to model tabular data is still challenging. The first problem of tabular data is the categorical encoding scheme, in which each categorical value is represented as a one-hot vector. It leads to the problem of very sparse high dimensional input space, especially when the cardinality of values of each attribute is high. This is problematic to GAN training since a trivial discriminator can simply distinguish real and fake data by checking the distributions sparseness. The second problem in tabular data is its hard constraint and discrete signals property which is challenging for neural networks. The modelling of discrete features is often associated with counting problem where gradient signals are not well-prepared for. As a result, current GAN methods might overlook and ignore these discrete features causing the mode-collapse in tabular data modelling. In this paper, we propose a unified framework to solve these two problems: (i) we propose to embed the raw data into the highlevel features and train GAN these features instead to avoid the trivial sparseness detection by the discriminator (ii) we propose the graphical-conditional vector to encourage GAN to learn to generate the structure information across multiple attributes. The experimental results show that our proposed methods perform much better than the current state-of-the-art method on most tabular benchmark datasets. Source code is available at: https://github.com/dungdinhanh/GDEGAN

This paper considers a variant of the Vehicle Routing Problem with Drones applied in the door-to-door sampling service system. Given a set of technicians and a fleet of drones departing from a medical center and working independently, the objective consists in designing feasible trips for technicians and drones such that the time from collection to arrival at the medical center of each customer’s test kits is not exceeded a limited duration and minimal makespan is achieved. A mixed-integer linear program (MILP) model is presented and solved to optimality with small instances due to the computational complexity of this problem. Thus, a tabu search approach is proposed. Experiments are then carried out to demonstrate the performance of the proposed algorithm and the advantage of integrating drones into the sampling service system.

Given a connected, weighted, undirected graph G=(V, E) and a bound D, bounded diameter minimum spanning tree problem (BDMST) seeks spanning tree on G with smallest weight in which no path between two vertices contains more than D edges. This problem is NP-hard for 4 les D les |V| - 1. This paper proposes three new multi-parent recombination operators using different methods to choose parents in genetic algorithm for solving bounded diameter minimum spanning tree problem. Results of computational experiments are reported to show the efficiency of proposed algorithms.