Author name cluster

My T. Thai

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

26 papers

2 author rows

NeurIPS Conference 2025 Conference Paper

Advancing Interpretability of CLIP Representations with Concept Surrogate Model

Nhat Hoang-Xuan
Xiyuan Wei
Wanli Xing
Tianbao Yang
My T. Thai

Contrastive Language-Image Pre-training (CLIP) generates versatile multimodal embeddings for diverse applications, yet the specific information captured within these representations is not fully understood. Current explainability techniques often target specific tasks, overlooking the rich, general semantics inherent in the representations. Our objective is to reveal the concepts encoded in CLIP embeddings by learning a surrogate representation, which is expressed as a linear combination of human-understandable concepts evident in the image. Our method, which we term EXPLAIN-R, introduces a novel approach that leverages CLIP's learned instance-instance similarity to train a surrogate model that faithfully mimics CLIP's behavior. From the trained surrogate, we derive concept scores for each input image; these scores quantify the contribution of each concept and act as the explanation for the representation. Quantitative evaluations on multiple datasets demonstrate our method's superior faithfulness over the baseline. Moreover, a user study confirms that our explanations are perceived as more relevant, complete, and useful. Our work provides a novel approach for interpreting CLIP image representations, enhancing the user interpretability of representations and fostering more trustworthy AI systems.

PDF Details

JMLR Journal 2025 Journal Article

EMaP: Explainable AI with Manifold-based Perturbations

Minh Nhat Vu
Huy Quang Mai
My T. Thai

In the last few years, many explanation methods based on the perturbations of input data have been introduced to shed light on the predictions generated by black-box models. The goal of this work is to introduce a novel perturbation scheme so that more faithful and robust explanations can be obtained. Our study focuses on the impact of perturbing directions on the data topology. We show that perturbing along the orthogonal directions of the input manifold better preserves the data topology, both in the worst-case analysis of the discrete Gromov-Hausdorff distance and in the average-case analysis via persistent homology. From those results, we introduce EMaP algorithm, realizing the orthogonal perturbation scheme. Our experiments show that EMaP not only improves the explainers' performance but also helps them overcome a recently developed attack against perturbation-based explanation methods. [abs] [ pdf ][ bib ] &copy JMLR 2025. ( edit, beta )

PDF Details

NeurIPS Conference 2025 Conference Paper

Hephaestus: Mixture Generative Modeling with Energy Guidance for Large-scale QoS Degradation

Nguyen Do
Bach Ngo
Youval Kashuv
Canh Pham
Hanghang Tong
My T. Thai

We study the Quality of Service Degradation (QoSD) problem, in which an adversary perturbs edge weights to degrade network performance. This setting arises in both network infrastructures and distributed ML systems, where communication quality, not just connectivity, determines functionality. While classical methods rely on combinatorial optimization, and recent ML approaches address only restricted linear variants with small-size networks, no prior model directly tackles the QoSD problem under nonlinear edge-weight functions. This work proposes Hephaestus, a self-reinforcing generative framework that synthesizes feasible solutions in latent space, to fill this gap. Our method includes three phases: (1) Forge: a Predictive Path-Stressing (PPS) algorithm that uses graph learning and approximation to produce feasible solutions with performance guarantee, (2) Morph: a new theoretically grounded training paradigm for Mixture of Conditional VAEs guided by an energy-based model to capture solution feature distributions, and (3) Refine: a reinforcement learning agent that explores this space to generate progressively near-optimal solutions using our designed differentiable reward function. Experiments on both synthetic and real-world networks show that our approach consistently outperforms classical and ML baselines, particularly in scenarios with nonlinear cost functions where traditional methods fail to generalize.

PDF Details

AAAI Conference 2025 Conference Paper

Metric-Agnostic Continual Learning for Sustainable Group Fairness

Heng Lian
Chen Zhao
Zhong Chen
Xingquan Zhu
My T. Thai
Yi He

Group Fairness-aware Continual Learning (GFCL) aims to eradicate discriminatory predictions against certain demographic groups in a sequence of diverse learning tasks. This paper explores an even more challenging GFCL problem – how to sustain a fair classifier across a sequence of tasks with covariate shifts and unlabeled data. We propose the MacFRL solution, with its key idea to optimize the sequence of learning tasks. We hypothesize that high-confident learning can be enabled in the optimized task sequence, where the classifier learns from a set of prioritized tasks to glean knowledge, thereby becoming more capable to handle the tasks with substantial distribution shifts that were originally deferred. Theoretical and empirical studies substantiate that MacFRL excels among its GFCL competitors in terms of prediction accuracy and group fair-ness metrics.

PDF Details DOI

ICML Conference 2025 Conference Paper

Model Steering: Learning with a Reference Model Improves Generalization Bounds and Scaling Laws

Xiyuan Wei
Ming Lin 0002
Fanjiang Ye
Fengguang Song
Liangliang Cao
My T. Thai
Tianbao Yang

This paper formalizes an emerging learning paradigm that uses a trained model as a reference to guide and enhance the training of a target model through strategic data selection or weighting, named model steering. While ad-hoc methods have been used in various contexts, including the training of large foundation models, its underlying principles remain insufficiently understood, leading to sub-optimal performance. In this work, we propose a theory-driven framework for model steering called DRRho risk minimization, which is rooted in Distributionally Robust Optimization (DRO). Through a generalization analysis, we provide theoretical insights into why this approach improves generalization and data efficiency compared to training without a reference model. To the best of our knowledge, this is the first time such theoretical insights are provided for the new learning paradigm, which significantly enhance our understanding and practice of model steering. Building on these insights and the connection between contrastive learning and DRO, we introduce a novel method for Contrastive Language-Image Pretraining (CLIP) with a reference model, termed DRRho-CLIP. Extensive experiments validate the theoretical insights, reveal a superior scaling law compared to CLIP without a reference model, and demonstrate its strength over existing heuristic approaches. Code is released at github. com/Optimization-AI/DRRho-CLIP

Details

ICLR Conference 2025 Conference Paper

NeurFlow: Interpreting Neural Networks through Neuron Groups and Functional Interactions

Tue Minh Cao
Nhat Hoang-Xuan
Hieu H. Pham 0001
Phi Le Nguyen
My T. Thai

Understanding the inner workings of neural networks is essential for enhancing model performance and interpretability. Current research predominantly focuses on examining the connection between individual neurons and the model's final predictions, which suffers from challenges in interpreting the internal workings of the model, particularly when neurons encode multiple unrelated features. In this paper, we propose a novel framework that transitions the focus from analyzing individual neurons to investigating groups of neurons, shifting the emphasis from neuron-output relationships to the functional interactions between neurons. Our automated framework, NeurFlow, first identifies core neurons and clusters them into groups based on shared functional relationships, enabling a more coherent and interpretable view of the network’s internal processes. This approach facilitates the construction of a hierarchical circuit representing neuron interactions across layers, thus improving interpretability while reducing computational costs. Our extensive empirical studies validate the fidelity of our proposed NeurFlow. Additionally, we showcase its utility in practical applications such as image debugging and automatic concept labeling, thereby highlighting its potential to advance the field of neural network explainability.

Details

TMLR Journal 2025 Journal Article

Stochastic Primal-Dual Double Block-Coordinate for Two- way Partial AUC Maximization

Linli Zhou
Bokun Wang
My T. Thai
Tianbao Yang

Two-way partial AUC (TPAUC) is a critical performance metric for binary classification with imbalanced data, as it focuses on specific ranges of the true positive rate (TPR) and false positive rate (FPR). However, stochastic algorithms for TPAUC optimization remain under-explored, with existing methods either limited to approximated TPAUC loss functions or burdened by sub-optimal complexities. To overcome these limitations, we introduce two innovative stochastic primal-dual double block-coordinate algorithms for TPAUC maximization. These algorithms utilize stochastic block-coordinate updates for both the primal and dual variables, catering to both convex and non-convex settings. We provide theoretical convergence rate analyses, demonstrating significant improvements over prior approaches. Our experimental results, based on multiple benchmark datasets, validate the superior performance of our algorithms, showcasing faster convergence and better generalization. This work advances the state of the art in TPAUC optimization and offers practical tools for real-world machine learning applications.

PDF Details

ICLR Conference 2025 Conference Paper

Swift Hydra: Self-Reinforcing Generative Framework for Anomaly Detection with Multiple Mamba Models

Nguyen Hoang Khoi Do
Truc Nguyen
Malik Hassanaly
Raed Alharbi
Jung Taek Seo
My T. Thai

Despite a plethora of anomaly detection models developed over the years, their ability to generalize to unseen anomalies remains an issue, particularly in critical systems. This paper aims to address this challenge by introducing Swift Hydra, a new framework for training an anomaly detection method based on generative AI and reinforcement learning (RL). Through featuring an RL policy that operates on the latent variables of a generative model, the framework synthesizes novel and diverse anomaly samples that are capable of bypassing a detection model. These generated synthetic samples are, in turn, used to augment the detection model, further improving its ability to handle challenging anomalies. Swift Hydra also incorporates Mamba models structured as a Mixture of Experts (MoE) to enable scalable adaptation of the number of Mamba experts based on data complexity, effectively capturing diverse feature distributions without increasing the model’s inference time. Empirical evaluations on ADBench benchmark demonstrate that Swift Hydra outperforms other state-of-the-art anomaly detection models while maintaining a relatively short inference time. From these results, our research highlights a new and auspicious paradigm of integrating RL and generative AI for advancing anomaly detection.

Details

ICML Conference 2025 Conference Paper

Theoretically Unmasking Inference Attacks Against LDP-Protected Clients in Federated Vision Models

Quan Minh Nguyen
Minh N. Vu
Truc Nguyen
My T. Thai

Federated Learning (FL) enables collaborative learning among clients via a coordinating server while avoiding direct data sharing, offering a perceived solution to preserve privacy. However, recent studies on Membership Inference Attacks (MIAs) have challenged this notion, showing high success rates against unprotected training data. While local differential privacy (LDP) is widely regarded as a gold standard for privacy protection in data analysis, most studies on MIAs either neglect LDP or fail to provide theoretical guarantees for attack success against LDP-protected data. To address this gap, we derive theoretical lower bounds for the success rates of low-polynomial-time MIAs that exploit vulnerabilities in fully connected or self-attention layers, regardless of the LDP mechanism used. We establish that even when data are protected by LDP, privacy risks persist, depending on the privacy budget. Practical evaluations on models like ResNet and Vision Transformer confirm considerable privacy risks, revealing that the noise required to mitigate these attacks significantly degrades models’ utility.

Details

AAAI Conference 2025 Conference Paper

XTSFormer: Cross-Temporal-Scale Transformer for Irregular-Time Event Prediction in Clinical Applications

Tingsong Xiao
Zelin Xu
Wenchong He
Zhengkun Xiao
Yupu Zhang
Zibo Liu
Shigang Chen
My T. Thai

Adverse clinical events related to unsafe care are among the top ten causes of death in the U.S. Accurate modeling and prediction of clinical events from electronic health records (EHRs) play a crucial role in patient safety enhancement. An example is modeling de facto care pathways that characterize common step-by-step plans for treatment or care. However, clinical event data pose several unique challenges, including the irregularity of time intervals between consecutive events, the existence of cycles, periodicity, multi-scale event interactions, and the high computational costs associated with long event sequences. Existing neural temporal point processes (TPPs) methods do not effectively capture the multi-scale nature of event interactions, which is common in many real-world clinical applications. To address these issues, we propose the cross-temporal-scale transformer (XTSFormer), specifically designed for irregularly timed event data. Our model consists of two vital components: a novel Feature-based Cycle-aware Time Positional Encoding (FCPE) that adeptly captures the cyclical nature of time, and a hierarchical multi-scale temporal attention mechanism, where different temporal scales are determined by a bottom-up clustering approach. Extensive experiments on several real-world EHR datasets show that our XTSFormer outperforms multiple baseline methods.

PDF Details DOI

NeurIPS Conference 2024 Conference Paper

Probabilistic Federated Prompt-Tuning with Non-IID and Imbalanced Data

Pei-Yau Weng
Minh Hoang
Lam M. Nguyen
My T. Thai
Tsui-Wei Weng
Trong N. Hoang

Fine-tuning pre-trained models is a popular approach in machine learning for solving complex tasks with moderate data. However, fine-tuning the entire pre-trained model is ineffective in federated data scenarios where local data distributions are diversely skewed. To address this, we explore integrating federated learning with a more effective prompt-tuning method, optimizing for a small set of input prefixes to reprogram the pre-trained model's behavior. Our approach transforms federated learning into a distributed set modeling task, aggregating diverse sets of prompts to globally fine-tune the pre-trained model. We benchmark various baselines based on direct adaptations of existing federated model aggregation techniques and introduce a new probabilistic prompt aggregation method that substantially outperforms these baselines. Our reported results on a variety of computer vision datasets confirm that the proposed method is most effective to combat extreme data heterogeneity in federated learning.

PDF Details DOI

ICML Conference 2023 Conference Paper

Deep Graph Representation Learning and Optimization for Influence Maximization

Chen Ling 0003
Junji Jiang
Junxiang Wang
My T. Thai
Renhao Xue
James Song
Meikang Qiu
Liang Zhao 0002

Influence maximization (IM) is formulated as selecting a set of initial users from a social network to maximize the expected number of influenced users. Researchers have made great progresses to design various traditional methods, yet both theoretical design and performance gain are close to their limits. In the past few years, learning-based IM methods have emerged to achieve stronger generalization ability to unknown graphs than traditional ones. However, the development of learning-based IM methods is still limited by fundamental obstacles, including 1) the difficulty of effectively solving the objective function; 2) the difficulty of characterizing the diversified and underlying diffusion patterns; and 3) the difficulty of adapting the solution under various node-centrality-constrained IM variants. To cope with the above challenges, we design a novel framework DeepIM to generatively characterize the latent representation of seed sets, and we propose to learn the diversified information diffusion pattern in a data-driven and end-to-end manner. Finally, we design a novel objective function to infer optimal seed sets under flexible node-centrality-based budget constraints. Extensive analyses are conducted over both synthetic and real-world datasets to demonstrate the overall performance of DeepIM.

Details

IJCAI Conference 2023 Conference Paper

Linear Query Approximation Algorithms for Non-monotone Submodular Maximization under Knapsack Constraint

Canh V. Pham
Tan D. Tran
Dung T. K. Ha
My T. Thai

This work, for the first time, introduces two constant factor approximation algorithms with linear query complexity for non-monotone submodular maximization over a ground set of size n subject to a knapsack constraint, DLA and RLA. DLA is a deterministic algorithm that provides an approximation factor of nearly 6 while RLA is a randomized algorithm with an approximation factor of nearly 4. Both run in linear query complexity. The key idea to obtain a constant approximation ratio with linear query lies in: (1) dividing the ground set into two appropriate subsets to find the near-optimal solution over these subsets with linear queries, and (2) combining a threshold greedy with properties of two disjoint sets or a random selection process to improve solution quality. In addition to the theoretical analysis, we have evaluated our proposed solutions with three applications: Revenue Maximization, Image Summarization, and Maximum Weighted Cut, showing that our algorithms not only return comparative results to state-of-the-art algorithms but also require significantly fewer queries.

PDF Details DOI

AAAI Conference 2023 Conference Paper

XRand: Differentially Private Defense against Explanation-Guided Attacks

Truc Nguyen
Phung Lai
Hai Phan
My T. Thai

Recent development in the field of explainable artificial intelligence (XAI) has helped improve trust in Machine-Learning-as-a-Service (MLaaS) systems, in which an explanation is provided together with the model prediction in response to each query. However, XAI also opens a door for adversaries to gain insights into the black-box models in MLaaS, thereby making the models more vulnerable to several attacks. For example, feature-based explanations (e.g., SHAP) could expose the top important features that a black-box model focuses on. Such disclosure has been exploited to craft effective backdoor triggers against malware classifiers. To address this trade-off, we introduce a new concept of achieving local differential privacy (LDP) in the explanations, and from that we establish a defense, called XRand, against such attacks. We show that our mechanism restricts the information that the adversary can learn about the top important features, while maintaining the faithfulness of the explanations.

PDF Details DOI

IJCAI Conference 2022 Conference Paper

Efficient Algorithms for Monotone Non-Submodular Maximization with Partition Matroid Constraint

Lan N. Nguyen
My T. Thai

In this work, we study the problem of monotone non-submodular maximization with partition matroid constraint. Although a generalization of this problem has been studied in literature, our work focuses on leveraging properties of partition matroid constraint to (1) propose algorithms with theoretical bound and efficient query complexity; and (2) provide better analysis on theoretical performance guarantee of some existing techniques. We further investigate those algorithms' performance in two applications: Boosting Influence Spread and Video Summarization. Experiments show our algorithms return comparative results to the state-of-the-art algorithms while taking much fewer queries.

PDF Details DOI

AAAI Conference 2021 Conference Paper

Minimum Robust Multi-Submodular Cover for Fairness

Lan N. Nguyen
My T. Thai

In this paper, we study a novel problem, Minimum Robust Multi-Submodular Cover for Fairness (MINRF), as follows: given a ground set V; m monotone submodular functions f1, .. ., fm; m thresholds T1, .. ., Tm and a non-negative integer r, MINRF asks for the smallest set S such that for all i ∈ [m], min|X|≤r fi(S \ X) ≥ Ti. We prove that MINRF is inapproximable within (1 − ) ln m; and no algorithm, taking fewer than exponential number of queries in term of r, is able to output a feasible set to MINRF with high certainty. Three bicriteria approximation algorithms with performance guarantees are proposed: one for r = 0, one for r = 1, and one for general r. We further investigate our algorithms’ performance in two applications of MINRF, Information Propagation for Multiple Groups and Movie Recommendation for Multiple Users. Our algorithms have shown to outperform baseline heuristics in both solution quality and the number of queries in most cases.

PDF Details

NeurIPS Conference 2020 Conference Paper

PGM-Explainer: Probabilistic Graphical Model Explanations for Graph Neural Networks

Minh Vu
My T. Thai

In Graph Neural Networks (GNNs), the graph structure is incorporated into the learning of node representations. This complex structure makes explaining GNNs' predictions become much more challenging. In this paper, we propose PGM-Explainer, a Probabilistic Graphical Model (PGM) model-agnostic explainer for GNNs. Given a prediction to be explained, PGM-Explainer identifies crucial graph components and generates an explanation in form of a PGM approximating that prediction. Different from existing explainers for GNNs where the explanations are drawn from a set of linear functions of explained features, PGM-Explainer is able to demonstrate the dependencies of explained features in form of conditional probabilities. Our theoretical analysis shows that the PGM generated by PGM-Explainer includes the Markov-blanket of the target prediction, i. e. including all its statistical information. We also show that the explanation returned by PGM-Explainer contains the same set of independence statements in the perfect map. Our experiments on both synthetic and real-world datasets show that PGM-Explainer achieves better performance than existing explainers in many benchmark tasks.

PDF Details

ICML Conference 2020 Conference Paper

Scalable Differential Privacy with Certified Robustness in Adversarial Learning

NhatHai Phan
My T. Thai
Han Hu 0007
Ruoming Jin
Tong Sun 0005
Dejing Dou

In this paper, we aim to develop a scalable algorithm to preserve differential privacy (DP) in adversarial learning for deep neural networks (DNNs), with certified robustness to adversarial examples. By leveraging the sequential composition theory in DP, we randomize both input and latent spaces to strengthen our certified robustness bounds. To address the trade-off among model utility, privacy loss, and robustness, we design an original adversarial objective function, based on the post-processing property in DP, to tighten the sensitivity of our model. A new stochastic batch training is proposed to apply our mechanism on large DNNs and datasets, by bypassing the vanilla iterative batch-by-batch training in DP DNNs. An end-to-end theoretical analysis and evaluations show that our mechanism notably improves the robustness and scalability of DP DNNs.

Details

ICML Conference 2020 Conference Paper

Streaming k-Submodular Maximization under Noise subject to Size Constraint

Lan Nguyen
My T. Thai

Maximizing on k-submodular functions subject to size constraint has received extensive attention recently. In this paper, we investigate a more realistic scenario of this problem that (1) obtaining exact evaluation of an objective function is impractical, instead, its noisy version is acquired; and (2) algorithms are required to take only one single pass over dataset, producing solutions in a timely manner. We propose two novel streaming algorithms, namely DStream and RStream, with their theoretical performance guarantees. We further demonstrate the efficiency of our algorithms in two application, showing that our algorithms can return comparative results to state-of-the-art non-streaming methods while using a much fewer number of queries.

Details

IJCAI Conference 2019 Conference Paper

Heterogeneous Gaussian Mechanism: Preserving Differential Privacy in Deep Learning with Provable Robustness

NhatHai Phan
Minh N. Vu
Yang Liu
Ruoming Jin
Dejing Dou
Xintao Wu
My T. Thai

In this paper, we propose a novel Heterogeneous Gaussian Mechanism (HGM) to preserve differential privacy in deep neural networks, with provable robustness against adversarial examples. We first relax the constraint of the privacy budget in the traditional Gaussian Mechanism from (0, 1] to (0, infty), with a new bound of the noise scale to preserve differential privacy. The noise in our mechanism can be arbitrarily redistributed, offering a distinctive ability to address the trade-off between model utility and privacy loss. To derive provable robustness, our HGM is applied to inject Gaussian noise into the first hidden layer. Then, a tighter robustness bound is proposed. Theoretical analysis and thorough evaluations show that our mechanism notably improves the robustness of differentially private deep neural networks, compared with baseline approaches, under a variety of model attacks.

PDF Details

ICML Conference 2019 Conference Paper

Submodular Cost Submodular Cover with an Approximate Oracle

Victoria G. Crawford
Alan Kuhnle
My T. Thai

In this work, we study the Submodular Cost Submodular Cover problem, which is to minimize the submodular cost required to ensure that the submodular benefit function exceeds a given threshold. Existing approximation ratios for the greedy algorithm assume a value oracle to the benefit function. However, access to a value oracle is not a realistic assumption for many applications of this problem, where the benefit function is difficult to compute. We present two incomparable approximation ratios for this problem with an approximate value oracle and demonstrate that the ratios take on empirically relevant values through a case study with the Influence Threshold problem in online social networks.

Details

ICML Conference 2018 Conference Paper

Fast Maximization of Non-Submodular, Monotonic Functions on the Integer Lattice

Alan Kuhnle
J. David Smith
Victoria G. Crawford
My T. Thai

The optimization of submodular functions on the integer lattice has received much attention recently, but the objective functions of many applications are non-submodular. We provide two approximation algorithms for maximizing a non-submodular function on the integer lattice subject to a cardinality constraint; these are the first algorithms for this purpose that have polynomial query complexity. We propose a general framework for influence maximization on the integer lattice that generalizes prior works on this topic, and we demonstrate the efficiency of our algorithms in this context.

Details

TCS Journal 2016 Journal Article

Optimal packet scan against malicious attacks in smart grids

Subhankar Mishra
Thang N. Dinh
My T. Thai
Jungtaek Seo
Incheol Shin

With the integration of advanced computing and communication technologies, the Smart Grid is expected to greatly enhance efficiency and reliability of future power systems with renewable energy resources, as well as distributed intelligence and demand response. Along with the salient features of the Smart Grid, cyber security emerges to be a critical issue because millions of electronic devices are inter-connected via communication networks throughout critical power facilities, which has an immediate impact on reliability of such a widespread infrastructure. In this paper, we discuss the packet based attacks and study the Optimal Inspection Points (OIP) problem, which asks us to find a subset of nodes in a given network to perform the Deep Packet Inspection so as to maximize the number of scanned packets while satisfying the delay constraints. This problem finds many applications for malicious attack detection, especially for those cases where each single packet or the network traffic is required to be inspected. Accordingly, we prove OIP is NP-complete and provide an FPTAS in the case of single path routing. For the multiple path routings, we design an FPTAS when the routing graph takes a form of series-parallel graphs, which is commonly used to model electric networks. We also discuss the multi-scan scenario and design PIVOT algorithm to tackle the problem and evaluate the algorithms through experiments.

Details DOI

TCS Journal 2015 Journal Article

Catastrophic cascading failures in power networks

Jungtaek Seo
Subhankar Mishra
Xiang Li
My T. Thai

The high demand of electricity makes power networks more vulnerable under cascading failures. Because of the operational dependencies between nodes, the failure of a small set of nodes can cause a large cascade of failures which results in the breakdown of the network. Thus, it is crucial to study the vulnerability of the power network under the cascading failures. In this paper, we study the cascading critical node (CasCN) problem which asks to find a set of nodes whose failure maximizes the number of failed nodes under the effect of cascading failures. We first show that the problem is NP-hard to approximate within the factor of O ( n 1 − ϵ ). We then design a new metric to evaluate the importance of nodes in the network and use it as the base to design the Fully Adaptive Cascading Potential algorithm. In the case where the network is robust, we propose an alternative algorithm, the Cooperating Attack algorithm, which includes several novel properties to solve the problem. Simulation results demonstrate the efficiency of proposed algorithms and provide more insight into the vulnerability of the power network.

Details DOI

TCS Journal 2012 Journal Article

New techniques for approximating optimal substructure problems in power-law graphs

Yilin Shen
Dung T. Nguyen
Ying Xuan
My T. Thai

The remarkable discovery of many large-scale real networks is the power-law distribution in degree sequence: the number of vertices with degree i is proportional to i − β for some constant β > 1. A lot of researchers believe that it may be easier to solve some optimization problems in power-law graphs. Unfortunately, many problems have been proved NP-hard even in power-law graphs. Intuitively, a theoretical question is raised: are these problems on power-law graphs still as hard as on general graphs? In this paper, we show that many optimal substructure problems, such as Minimum Dominating Set, Minimum Vertex Cover and Maximum Independent Set, are easier to solve in power-law graphs by illustrating better inapproximability factors. An optimization problem has the property of optimal substructure if its optimal solution on some given graph is essentially the union of the optimal sub-solutions on all maximal connected components. In particular, we prove the above problems and a more general problem ( ρ -Minimum Dominating Set) remain APX-hard and their constant inapproximability factors on general power-law graphs by using the cycle-based embedding technique to embed any d -bounded graphs into a power-law graph. In addition, in simple power-law graphs, we further prove the corresponding inapproximability factors of these problems based on the graphic embedding technique as well as that of Maximum Clique and Minimum Coloring using the embedding technique in [1]. As a result of these inapproximability factors, the belief that there exists some ( 1 + o ( 1 ) ) -approximation algorithm for these problems on power-law graphs is proven to be not always true. At last, we do in-depth investigations in the relationship between the exponential factor β and constant greedy approximation algorithms.

Details DOI

TCS Journal 2007 Journal Article

On approximation algorithms of k -connected m -dominating sets in disk graphs

My T. Thai
Ning Zhang
Ravi Tiwari
Xiaochun Xu

Connected Dominating Set (CDS) has been proposed as the virtual backbone to alleviate the broadcasting storm in wireless ad hoc networks. Most recent research has extensively focused on the construction of 1-Connected 1-Dominating Set (1-CDS) in homogeneous networks. However, the nodes in the CDS need to carry other node’s traffic and nodes in wireless networks are subject to failure. Therefore, it is desirable to construct a fault tolerant CDS. In this paper, we study a general fault tolerant CDS problem, called k -Connected m -Dominating Set ( k - m -CDS), in heterogeneous networks. We first present two approximation algorithms for 1- m -CDS and k - k -CDS problems. Using disk graphs to model heterogeneous networks, we show that our algorithms have a constant approximation ratio. Based on these two algorithms, we further develop a general algorithm for k - m -CDS. We also provide an interesting analysis for a special case of k - m -CDS, where k = m + 1.

Details DOI