Showing 1–50 of 87 results for author: Das, G

DSCA: Dynamic Subspace Concept Alignment for Lifelong VLM Editing

Authors: Gyanendra Das, Sai Satyam Jena

Abstract: Model editing aims to update knowledge to add new concepts and change relevant information without retraining. Lifelong editing is a challenging task, prone to disrupting previously learned concepts, especially for Vision Language Models (VLMs), because sequential edits can lead to degraded reasoning and cross modal misalignment. Existing VLM knowledge editing methods based on gated adapters, acti… ▽ More Model editing aims to update knowledge to add new concepts and change relevant information without retraining. Lifelong editing is a challenging task, prone to disrupting previously learned concepts, especially for Vision Language Models (VLMs), because sequential edits can lead to degraded reasoning and cross modal misalignment. Existing VLM knowledge editing methods based on gated adapters, activation edits, and parameter merging techniques address catastrophic forgetting seen in full fine tuning; however, they still operate in the shared representation space of the VLM, where concepts are entangled, so edits interfere with other non relevant concepts. We hypothesize that this instability persists because current methods algorithmically control edits via optimization rather than structurally separating knowledge. We introduce Dynamic Subspace Concept Alignment (DSCA) which by design mitigates this limitation by decomposing the representation space into a set of orthogonal semantic subspaces and proposing edits only in those transformed spaces. These subspaces are obtained through incremental clustering and PCA on joint vision language representations. This process structurally isolates concepts, enabling precise, non interfering edits by turning isolation from a soft training objective into an architectural property. The surgical edits are guided by a multi term loss function for maintaining task fidelity, edit locality, and cross modal alignment. With the base model frozen, our method achieves 98 percent single edit success, remains over 95 percent after 1000 sequential edits, lowers hallucination by 3 to 5 percent, and achieves the best backward transfer (BWT) scores on continual instruction tuning benchmarks. Extensive experiments demonstrate DSCA state of the art stability and knowledge retention capability in continual lifelong editing across various datasets and benchmarks. △ Less

Submitted 9 April, 2026; originally announced April 2026.

Comments: Accepted at CVPR 2026

Game-Theory-Assisted Reinforcement Learning for Border Defense: Early Termination based on Analytical Solutions

Authors: Goutam Das, Michael Dorothy, Kyle Volle, Daigo Shishika

Abstract: Game theory provides the gold standard for analyzing adversarial engagements, offering strong optimality guarantees. However, these guarantees often become brittle when assumptions such as perfect information are violated. Reinforcement learning (RL), by contrast, is adaptive but can be sample-inefficient in large, complex domains. This paper introduces a hybrid approach that leverages game-theore… ▽ More Game theory provides the gold standard for analyzing adversarial engagements, offering strong optimality guarantees. However, these guarantees often become brittle when assumptions such as perfect information are violated. Reinforcement learning (RL), by contrast, is adaptive but can be sample-inefficient in large, complex domains. This paper introduces a hybrid approach that leverages game-theoretic insights to improve RL training efficiency. We study a border defense game with limited perceptual range, where defender performance depends on both search and pursuit strategies, making classical differential game solutions inapplicable. Our method employs the Apollonius Circle (AC) to compute equilibrium in the post-detection phase, enabling early termination of RL episodes without learning pursuit dynamics. This allows RL to concentrate on learning search strategies while guaranteeing optimal continuation after detection. Across single- and multi-defender settings, this early termination method yields 10-20% higher rewards, faster convergence, and more efficient search trajectories. Extensive experiments validate these findings and demonstrate the overall effectiveness of our approach. △ Less

Submitted 16 March, 2026; originally announced March 2026.

Comments: 7 pages, ACC 2026

Route Fragmentation Based on Resource-centric Prioritisation for Efficient Multi-Robot Path Planning in Agricultural Environments

Authors: James R. Heselden, Gautham P. Das

Abstract: Agricultural environments present high proportions of spatially dense navigation bottlenecks for long-term navigation and operational planning of agricultural mobile robots. The existing agent-centric multi-robot path planning (MRPP) approaches resolve conflicts from the perspective of agents, rather than from the resources under contention. Further, the density of such contentions limits the capa… ▽ More Agricultural environments present high proportions of spatially dense navigation bottlenecks for long-term navigation and operational planning of agricultural mobile robots. The existing agent-centric multi-robot path planning (MRPP) approaches resolve conflicts from the perspective of agents, rather than from the resources under contention. Further, the density of such contentions limits the capabilities of spatial interleaving, a concept that many planners rely on to achieve high throughput. In this work, two variants of the priority-based Fragment Planner (FP) are presented as resource-centric MRPP algorithms that leverage route fragmentation to enable partial route progression and limit the impact of binary-based waiting. These approaches are evaluated in lifelong simulation over a 3.6km topological map representing a commercial polytunnel environment. Their performances are contrasted against 5 baseline algorithms with varying robotic fleet sizes. The Fragment Planners achieved significant gains in throughput compared with Prioritised Planning (PP) and Priority-Based Search (PBS) algorithms. They further demonstrated a task throughput of 95% of the optimal task throughput over the same time period. This work shows that, for long-term deployment of agricultural robots in corridor-dominant agricultural environments, resource-centric MRPP approaches are a necessity for high-efficacy operational planning. △ Less

Submitted 13 March, 2026; originally announced March 2026.

Comments: This work has been submitted to the IEEE for possible publication

Towards Understanding Best Practices for Quantization of Vision-Language Models

Authors: Gautom Das, Vincent La, Ethan Lau, Abhinav Shrivastava, Matthew Gwilliam

Abstract: Large language models (LLMs) deliver impressive results for a variety of tasks, but state-of-the-art systems require fast GPUs with large amounts of memory. To reduce both the memory and latency of these systems, practitioners quantize their learned parameters, typically at half precision. A growing body of research focuses on preserving the model performance with more aggressive bit widths, and s… ▽ More Large language models (LLMs) deliver impressive results for a variety of tasks, but state-of-the-art systems require fast GPUs with large amounts of memory. To reduce both the memory and latency of these systems, practitioners quantize their learned parameters, typically at half precision. A growing body of research focuses on preserving the model performance with more aggressive bit widths, and some work has been done to apply these strategies to other models, like vision transformers. In our study we investigate how a variety of quantization methods, including state-of-the-art GPTQ and AWQ, can be applied effectively to multimodal pipelines comprised of vision models, language models, and their connectors. We address how performance on captioning, retrieval, and question answering can be affected by bit width, quantization method, and which portion of the pipeline the quantization is used for. Results reveal that ViT and LLM exhibit comparable importance in model performance, despite significant differences in parameter size, and that lower-bit quantization of the LLM achieves high accuracy at reduced bits per weight (bpw). These findings provide practical insights for efficient deployment of MLLMs and highlight the value of exploration for understanding component sensitivities in multimodal models. Our code is available at https://github.com/gautomdas/mmq. △ Less

Submitted 21 January, 2026; originally announced January 2026.

Comments: 15 pages, 12 figures, 1 table

Scheduling for TWDM-EPON-Based Fronthaul Without a Dedicated Registration Wavelength

Authors: Akash Kumar, Sourav Dutta, Goutam Das

Abstract: The adoption of Centralized Radio Access Network (C-RAN) architectures requires fronthaul systems capable of carrying large volumes of radio data while meeting stringent delay and jitter requirements. Ethernet Passive Optical Networks (EPONs) have emerged as a promising fronthaul solution due to their cost efficiency and compatibility with existing infrastructure. However, the traditional registra… ▽ More The adoption of Centralized Radio Access Network (C-RAN) architectures requires fronthaul systems capable of carrying large volumes of radio data while meeting stringent delay and jitter requirements. Ethernet Passive Optical Networks (EPONs) have emerged as a promising fronthaul solution due to their cost efficiency and compatibility with existing infrastructure. However, the traditional registration process for EPON systems halts the ongoing data transmissions during the registration period, thereby violating the enhanced Common Public Radio Interface (eCPRI) delay and jitter requirements. This limitation has been acknowledged by the ITU-T, which recommends the use of a dedicated wavelength channel for registration, leading to inefficient bandwidth utilization. In this paper, we propose a novel scheduling framework for a Time and Wavelength Division Multiplexed (TWDM) EPON-based fronthaul that enables periodic registration without wasting an additional wavelength channel. Performance evaluation demonstrates that the proposed method achieves up to a 71\% increase in the number of Radio Units (RUs) supported for a given number of wavelength channels, compared to a baseline scheme employing a dedicated registration wavelength. △ Less

Submitted 24 January, 2026; v1 submitted 2 January, 2026; originally announced January 2026.

Comments: 9 pages, 9 figures

Cross-Task Benchmarking and Evaluation of General-Purpose and Code-Specific Large Language Models

Authors: Gunjan Das, Paheli Bhattacharya, Rishabh Gupta

Abstract: Large Language Models (LLMs) have revolutionized both general natural language processing and domain-specific applications such as code synthesis, legal reasoning, and finance. However, while prior studies have explored individual model capabilities, a systematic cross-domain comparison that unifies linguistic, reasoning, and code understanding abilities remains underexplored. In this work, we pre… ▽ More Large Language Models (LLMs) have revolutionized both general natural language processing and domain-specific applications such as code synthesis, legal reasoning, and finance. However, while prior studies have explored individual model capabilities, a systematic cross-domain comparison that unifies linguistic, reasoning, and code understanding abilities remains underexplored. In this work, we present a comprehensive evaluation of five general-purpose and three code-specific state-of-the-art LLMs across six diverse benchmarks encompassing linguistic competence, mathematical reasoning, and trustworthiness. Additionally, we analyze model behavior on the CoNaLa dataset for code explanation, comparing natural language and code-specialized LLMs. Our findings reveal that models optimized for code (e.g., CodeLLaMA variants) exhibit strong reasoning and syntactic precision, that even for non-coding tasks can show measurable performance gains, in contrast to general-purpose models like Mistral-7B and Llama-3-8B. △ Less

Submitted 4 December, 2025; originally announced December 2025.

Understanding and Utilizing Dynamic Coupling in Free-Floating Space Manipulators for On-Orbit Servicing

Authors: Gargi Das, Daegyun Choi, Donghoon Kim

Abstract: This study proposes a dynamic coupling-informed trajectory optimization algorithm for free-floating space manipulator systems (SMSs). Dynamic coupling between the base and the manipulator arms plays a critical role in influencing the system's behavior. While prior research has predominantly focused on minimizing this coupling, often overlooking its potential advantages, this work investigates how… ▽ More This study proposes a dynamic coupling-informed trajectory optimization algorithm for free-floating space manipulator systems (SMSs). Dynamic coupling between the base and the manipulator arms plays a critical role in influencing the system's behavior. While prior research has predominantly focused on minimizing this coupling, often overlooking its potential advantages, this work investigates how dynamic coupling can instead be leveraged to improve trajectory planning. Singular value decomposition (SVD) of the dynamic coupling matrix is employed to identify the dominant components governing coupling behavior. A quantitative metric is then formulated to characterize the strength and directionality of the coupling and is incorporated into a trajectory optimization framework. To assess the feasibility of the optimized trajectory, a sliding mode control-based tracking controller is designed to generate the required joint torque inputs. Simulation results demonstrate that explicitly accounting for dynamic coupling in trajectory planning enables more informed and potentially more efficient operation, offering new directions for the control of free-floating SMSs. △ Less

Submitted 21 August, 2025; originally announced August 2025.

Comments: 17 pages, 7 figures, 2025 AAS/AIAA Astrodynamics Specialist Conference

Efficient Direct-Access Ranked Retrieval

Authors: Mohsen Dehghankar, Raghav Mittal, Suraj Shetiya, Abolfazl Asudeh, Gautam Das

Abstract: We study the problem of Direct-Access Ranked Retrieval (DAR) for interactive data tooling, where evolving data exploration practices, combined with large-scale and high-dimensional datasets, create new challenges. DAR concerns the problem of enabling efficient access to arbitrary rank positions according to a ranking function, without enumerating all preceding tuples. To address this need, we form… ▽ More We study the problem of Direct-Access Ranked Retrieval (DAR) for interactive data tooling, where evolving data exploration practices, combined with large-scale and high-dimensional datasets, create new challenges. DAR concerns the problem of enabling efficient access to arbitrary rank positions according to a ranking function, without enumerating all preceding tuples. To address this need, we formalize the DAR problem and propose a theoretically efficient algorithm based on geometric arrangements, achieving logarithmic query time. However, this method suffers from exponential space complexity in high dimensions. Therefore, we develop a second class of algorithms based on $\varepsilon$-sampling, which consume a linear space. Since exactly locating the tuple at a specific rank is challenging due to its connection to the range counting problem, we introduce a relaxed variant called Conformal Set Ranked Retrieval (CSR), which returns a small subset guaranteed to contain the target tuple. To solve the CSR problem efficiently, we define an intermediate problem, Stripe Range Retrieval (SRR), and design a hierarchical sampling data structure tailored for narrow-range queries. Our method achieves practical scalability in both data size and dimensionality. We prove near-optimal bounds on the efficiency of our algorithms and validate their performance through extensive experiments on real and synthetic datasets, demonstrating scalability to millions of tuples and hundreds of dimensions. △ Less

Submitted 1 August, 2025; originally announced August 2025.

OpenScout v1.1 mobile robot: a case study on open hardware continuation

Authors: Bartosz Krawczyk, Ahmed Elbary, Robbie Cato, Jagdish Patil, Kaung Myat, Anyeh Ndi-Tah, Nivetha Sakthivel, Mark Crampton, Gautham Das, Charles Fox

Abstract: OpenScout is an Open Source Hardware (OSH) mobile robot for research and industry. It is extended to v1.1 which includes simplified, cheaper and more powerful onboard compute hardware; a simulated ROS2 interface; and a Gazebo simulation. Changes, their rationale, project methodology, and results are reported as an OSH case study. OpenScout is an Open Source Hardware (OSH) mobile robot for research and industry. It is extended to v1.1 which includes simplified, cheaper and more powerful onboard compute hardware; a simulated ROS2 interface; and a Gazebo simulation. Changes, their rationale, project methodology, and results are reported as an OSH case study. △ Less

Submitted 1 August, 2025; originally announced August 2025.

Comments: 6 pages, 4 figures, a TAROS2025 short paper

FairDeFace: Evaluating the Fairness and Adversarial Robustness of Face Obfuscation Methods

Authors: Seyyed Mohammad Sadegh Moosavi Khorzooghi, Poojitha Thota, Mohit Singhal, Abolfazl Asudeh, Gautam Das, Shirin Nilizadeh

Abstract: The lack of a common platform and benchmark datasets for evaluating face obfuscation methods has been a challenge, with every method being tested using arbitrary experiments, datasets, and metrics. While prior work has demonstrated that face recognition systems exhibit bias against some demographic groups, there exists a substantial gap in our understanding regarding the fairness of face obfuscati… ▽ More The lack of a common platform and benchmark datasets for evaluating face obfuscation methods has been a challenge, with every method being tested using arbitrary experiments, datasets, and metrics. While prior work has demonstrated that face recognition systems exhibit bias against some demographic groups, there exists a substantial gap in our understanding regarding the fairness of face obfuscation methods. Providing fair face obfuscation methods can ensure equitable protection across diverse demographic groups, especially since they can be used to preserve the privacy of vulnerable populations. To address these gaps, this paper introduces a comprehensive framework, named FairDeFace, designed to assess the adversarial robustness and fairness of face obfuscation methods. The framework introduces a set of modules encompassing data benchmarks, face detection and recognition algorithms, adversarial models, utility detection models, and fairness metrics. FairDeFace serves as a versatile platform where any face obfuscation method can be integrated, allowing for rigorous testing and comparison with other state-of-the-art methods. In its current implementation, FairDeFace incorporates 6 attacks, and several privacy, utility and fairness metrics. Using FairDeFace, and by conducting more than 500 experiments, we evaluated and compared the adversarial robustness of seven face obfuscation methods. This extensive analysis led to many interesting findings both in terms of the degree of robustness of existing methods and their biases against some gender or racial groups. FairDeFace also uses visualization of focused areas for both obfuscation and verification attacks to show not only which areas are mostly changed in the obfuscation process for some demographics, but also why they failed through focus area comparison of obfuscation and verification. △ Less

Submitted 10 March, 2025; originally announced March 2025.

(Independent) Roman Domination Parameterized by Distance to Cluster

Authors: Pradeesha Ashok, Gautam K. Das, Arti Pandey, Kaustav Paul, Subhabrata Paul

Abstract: Given a graph $G=(V,E)$, a function $f:V\to \{0,1,2\}$ is said to be a \emph{Roman Dominating function} (RDF) if for every $v\in V$ with $f(v)=0$, there exists a vertex $u\in N(v)$ such that $f(u)=2$. A Roman Dominating function $f$ is said to be an \emph{Independent Roman Dominating function} (IRDF), if $V_1\cup V_2$ forms an independent set, where $V_i=\{v\in V~\vert~f(v)=i\}$, for… ▽ More Given a graph $G=(V,E)$, a function $f:V\to \{0,1,2\}$ is said to be a \emph{Roman Dominating function} (RDF) if for every $v\in V$ with $f(v)=0$, there exists a vertex $u\in N(v)$ such that $f(u)=2$. A Roman Dominating function $f$ is said to be an \emph{Independent Roman Dominating function} (IRDF), if $V_1\cup V_2$ forms an independent set, where $V_i=\{v\in V~\vert~f(v)=i\}$, for $i\in \{0,1,2\}$. The total weight of $f$ is equal to $\sum_{v\in V} f(v)$, and is denoted as $w(f)$. The \emph{Roman Domination Number} (resp. \emph{Independent Roman Domination Number}) of $G$, denoted by $γ_R(G)$ (resp. $i_R(G)$), is defined as min$\{w(f)~\vert~f$ is an RDF (resp. IRDF) of $G\}$. For a given graph $G$, the problem of computing $γ_R(G)$ (resp. $i_R(G)$) is defined as the \emph{Roman Domination problem} (resp. \emph{Independent Roman Domination problem}). In this paper, we examine structural parameterizations of the (Independent) Roman Domination problem. We propose fixed-parameter tractable (FPT) algorithms for the (Independent) Roman Domination problem in graphs that are $k$ vertices away from a cluster graph. These graphs have a set of $k$ vertices whose removal results in a cluster graph. We refer to $k$ as the distance to the cluster graph. Specifically, we prove the following results when parameterized by the deletion distance $k$ to cluster graphs: we can find the Roman Domination Number (and Independent Roman Domination Number) in time $4^kn^{O(1)}$. In terms of lower bounds, we show that the Roman Domination number can not be computed in time $2^{εk}n^{O(1)}$, for any $0<ε<1$ unless a well-known conjecture, SETH fails. In addition, we also show that the Roman Domination problem parameterized by distance to cluster, does not admit a polynomial kernel unless NP $\subseteq$ coNP$/$poly. △ Less

Submitted 20 November, 2024; originally announced November 2024.

Comments: arXiv admin note: text overlap with arXiv:2405.10556 by other authors

Online RMLSA in EONs with $A^3G$: Adaptive ACO with Augmentation of Graph

Authors: M Jyothi Kiran, Venkatesh Chebolu, Goutam Das, Raja Datta

Abstract: Routing and Spectrum Assignment (RSA) represents a significant challenge within Elastic Optical Networks (EONs), particularly in dynamic traffic scenarios where the network undergoes continuous changes. Integrating multiple modulation formats transforms it into Routing Modulation Level and Spectrum Assignment (RMLSA) problem, thereby making it more challenging. Traditionally, addressing the RSA pr… ▽ More Routing and Spectrum Assignment (RSA) represents a significant challenge within Elastic Optical Networks (EONs), particularly in dynamic traffic scenarios where the network undergoes continuous changes. Integrating multiple modulation formats transforms it into Routing Modulation Level and Spectrum Assignment (RMLSA) problem, thereby making it more challenging. Traditionally, addressing the RSA problem involved identifying a fixed number of paths and subsequently allocating spectrum among them. Numerous heuristic and metaheuristic approaches have been proposed for RSA using this two-step methodology. However, solving for routing and assignment of spectrum independently is not recommended due to their interdependencies and their impact on resource utilization, fragmentation and bandwidth blocking probability. In this paper, we propose a novel approach to solve the RMLSA problem jointly in dynamic traffic scenarios, inspired by Ant Colony Optimization (ACO). This approach involves augmenting the network into an Auxiliary Graph and transforming conventional ACO into a constraint-based ACO variant that adapts to the constraints of EONs. This adaptation also includes an adaptive initiation process and an aggressive termination strategy aimed at achieving faster convergence. Moreover, we have introduced a novel objective/fitness function, to minimize average network fragmentation while ensuring optimal spectrum resource utilization, thereby reducing overall blocking probability. △ Less

Submitted 19 November, 2024; originally announced November 2024.

Comments: 11 pages, 10 figures

Guarding a Target Area from a Heterogeneous Group of Cooperative Attackers

Authors: Yoonjae Lee, Goutam Das, Daigo Shishika, Efstathios Bakolas

Abstract: In this paper, we investigate a multi-agent target guarding problem in which a single defender seeks to capture multiple attackers aiming to reach a high-value target area. In contrast to previous studies, the attackers herein are assumed to be heterogeneous in the sense that they have not only different speeds but also different weights representing their respective degrees of importance (e.g., t… ▽ More In this paper, we investigate a multi-agent target guarding problem in which a single defender seeks to capture multiple attackers aiming to reach a high-value target area. In contrast to previous studies, the attackers herein are assumed to be heterogeneous in the sense that they have not only different speeds but also different weights representing their respective degrees of importance (e.g., the amount of allocated resources). The objective of the attacker team is to jointly minimize the weighted sum of their final levels of proximity to the target area, whereas the defender aims to maximize the same value. Using geometric arguments, we construct candidate equilibrium control policies that require the solution of a (possibly nonconvex) optimization problem. Subsequently, we validate the optimality of the candidate control policies using parametric optimization techniques. Lastly, we provide numerical examples to illustrate how cooperative behaviors emerge within the attacker team due to their heterogeneity. △ Less

Submitted 30 June, 2024; originally announced July 2024.

Comments: This is the revised version of the paper, with the same title, to be presented at American Control Conference (ACC) 2024

Unified Map Handling for Robotic Systems: Enhancing Interoperability and Efficiency Across Diverse Environments

Authors: James R. Heselden, Gautham P. Das

Abstract: Mapping is a time-consuming process for deploying robotic systems to new environments. The handling of maps is also risk-adverse when not managed effectively. We propose here, a standardised approach to handling such maps in a manner which focuses on the information contained wherein such as global location, object positions, topology, and occupancy. As part of this approach, associated management… ▽ More Mapping is a time-consuming process for deploying robotic systems to new environments. The handling of maps is also risk-adverse when not managed effectively. We propose here, a standardised approach to handling such maps in a manner which focuses on the information contained wherein such as global location, object positions, topology, and occupancy. As part of this approach, associated management scripts are able to assist with generation of maps both through direct and indirect information restructuring, and with template and procedural generation of missing data. These approaches are able to, when combined, improve the handling of maps to enable more efficient deployments and higher interoperability between platforms. Alongside this, a collection of sample datasets of fully-mapped environments are included covering areas such as agriculture, urban roadways, and indoor environments. △ Less

Submitted 20 April, 2024; originally announced April 2024.

Comments: 6 pages, 5 figures, Accepted to the IEEE ICRA Workshop on Field Robotics 2024

ABACUS: An Impairment Aware Joint Optimal Dynamic RMLSA in Elastic Optical Networks

Authors: M Jyothi Kiran, Venkatesh Chebolu, Goutam Das, Raja Datta

Abstract: The challenge of optimal Routing and Spectrum Assignment (RSA) is significant in Elastic Optical Networks. Integrating adaptive modulation formats into the RSA problem - Routing, Modulation Level, and Spectrum Assignment - broadens allocation options and increases complexity. The conventional RSA approach entails predetermining fixed paths and then allocating spectrum within them separately. Howev… ▽ More The challenge of optimal Routing and Spectrum Assignment (RSA) is significant in Elastic Optical Networks. Integrating adaptive modulation formats into the RSA problem - Routing, Modulation Level, and Spectrum Assignment - broadens allocation options and increases complexity. The conventional RSA approach entails predetermining fixed paths and then allocating spectrum within them separately. However, expanding the path set for optimality may not be advisable due to the substantial increase in paths with network size expansion. This paper delves into a novel approach called RMLSA, which proposes a comprehensive solution addressing both route determination and spectrum assignment simultaneously. An objective function named ABACUS, Adaptive Balance of Average Clustering and Utilization of Spectrum, is chosen for its capability to adjust and assign significance to average clustering and spectrum utilization. Our approach involves formulating an Integer Linear Programming model with a straightforward relationship between path and spectrum constraints. The model also integrates Physical Layer Impairments to ensure end-to-end Quality of Transmission for requested connections while maintaining existing ones. We demonstrate that ILP can offer an optimal solution for a dynamic traffic scenario within a reasonable time complexity. To achieve this goal, we adopt a structured formulation approach where essential information is determined beforehand, thus minimizing the need for online computations. △ Less

Submitted 20 April, 2024; originally announced April 2024.

Improved Total Domination and Total Roman Domination in Unit Disk Graphs

Authors: Sasmita Rout, Gautam Kumar Das

Abstract: Let $G=(V, E)$ be a simple undirected graph with no isolated vertex. A set $D_t\subseteq V$ is a total dominating set of $G$ if $(i)$ $D_t$ is a dominating set, and $(ii)$ the set $D_t$ induces a subgraph with no isolated vertex. The total dominating set of minimum cardinality is called the minimum total dominating set, and the size of the minimum total dominating set is called the total dominatio… ▽ More Let $G=(V, E)$ be a simple undirected graph with no isolated vertex. A set $D_t\subseteq V$ is a total dominating set of $G$ if $(i)$ $D_t$ is a dominating set, and $(ii)$ the set $D_t$ induces a subgraph with no isolated vertex. The total dominating set of minimum cardinality is called the minimum total dominating set, and the size of the minimum total dominating set is called the total domination number ($γ_t(G)$). Given a graph $G$, the total dominating set (TDS) problem is to find a total dominating set of minimum cardinality. A Roman dominating function (RDF) on a graph $G$ is a function $f:V\rightarrow \{0,1,2\}$ such that each vertex $v\in V$ with $f(v)=0$ is adjacent to at least one vertex $u\in V$ with $f(u)=2$. A RDF $f$ of a graph $G$ is said to be a total Roman dominating function (TRDF) if the induced subgraph of $V_1\cup V_2$ does not contain any isolated vertex, where $V_i=\{u\in V|f(u)=i\}$. Given a graph $G$, the total Roman dominating set (TRDS) problem is to minimize the weight, $W(f)=\sum_{u\in V} f(u)$, called the total Roman domination number ($γ_{tR}(G)$). In this paper, we are the first to show that the TRDS problem is NP-complete in unit disk graphs (UDGs). Furthermore, we propose a $7.17\operatorname{-}$ factor approximation algorithm for the TDS problem and a $6.03\operatorname{-}$ factor approximation algorithm for the TRDS problem in geometric unit disk graphs. The running time for both algorithms is notably bounded by $O(n\log{k})$, where $n$ represents the number of vertices in the given UDG and $k$ represents the size of the independent set in (i.e., $D$ and $V_2$ in TDS and TRDS problems, respectively) the given UDG. △ Less

Submitted 4 April, 2024; originally announced April 2024.

AXOLOTL: Fairness through Assisted Self-Debiasing of Large Language Model Outputs

Authors: Sana Ebrahimi, Kaiwen Chen, Abolfazl Asudeh, Gautam Das, Nick Koudas

Abstract: Pre-trained Large Language Models (LLMs) have significantly advanced natural language processing capabilities but are susceptible to biases present in their training data, leading to unfair outcomes in various applications. While numerous strategies have been proposed to mitigate bias, they often require extensive computational resources and may compromise model performance. In this work, we intro… ▽ More Pre-trained Large Language Models (LLMs) have significantly advanced natural language processing capabilities but are susceptible to biases present in their training data, leading to unfair outcomes in various applications. While numerous strategies have been proposed to mitigate bias, they often require extensive computational resources and may compromise model performance. In this work, we introduce AXOLOTL, a novel post-processing framework, which operates agnostically across tasks and models, leveraging public APIs to interact with LLMs without direct access to internal parameters. Through a three-step process resembling zero-shot learning, AXOLOTL identifies biases, proposes resolutions, and guides the model to self-debias its outputs. This approach minimizes computational costs and preserves model performance, making AXOLOTL a promising tool for debiasing LLM outputs with broad applicability and ease of use. △ Less

Submitted 29 February, 2024; originally announced March 2024.

Near-perfect Coverage Manifold Estimation in Cellular Networks via conditional GAN

Authors: Washim Uddin Mondal, Veni Goyal, Satish V. Ukkusuri, Goutam Das, Di Wang, Mohamed-Slim Alouini, Vaneet Aggarwal

Abstract: This paper presents a conditional generative adversarial network (cGAN) that translates base station location (BSL) information of any Region-of-Interest (RoI) to location-dependent coverage probability values within a subset of that region, called the region-of-evaluation (RoE). We train our network utilizing the BSL data of India, the USA, Germany, and Brazil. In comparison to the state-of-the-a… ▽ More This paper presents a conditional generative adversarial network (cGAN) that translates base station location (BSL) information of any Region-of-Interest (RoI) to location-dependent coverage probability values within a subset of that region, called the region-of-evaluation (RoE). We train our network utilizing the BSL data of India, the USA, Germany, and Brazil. In comparison to the state-of-the-art convolutional neural networks (CNNs), our model improves the prediction error ($L_1$ difference between the coverage manifold generated by the network under consideration and that generated via simulation) by two orders of magnitude. Moreover, the cGAN-generated coverage manifolds appear to be almost visually indistinguishable from the ground truth. △ Less

Submitted 10 February, 2024; originally announced February 2024.

Journal ref: IEEE Networking Letters, 2024

TCP Slice: A semi-distributed TCP algorithm for Delay-constrained Applications

Authors: Dibbendu Roy, Goutam Das

Abstract: The TCP congestion control protocol serves as the cornerstone of reliable internet communication. However, as new applications require more specific guarantees regarding data rate and delay, network management must adapt. Thus, service providers are shifting from decentralized to centralized control of the network using a software-defined network controller (SDN). The SDN classifies applications a… ▽ More The TCP congestion control protocol serves as the cornerstone of reliable internet communication. However, as new applications require more specific guarantees regarding data rate and delay, network management must adapt. Thus, service providers are shifting from decentralized to centralized control of the network using a software-defined network controller (SDN). The SDN classifies applications and allocates logically separate resources called slices, over the physical network. We propose TCP Slice, a congestion control algorithm that meets specific delay and bandwidth guarantees. Obtaining closed-form delay bounds for a client is challenging due to dependencies on other clients and their traffic stochasticity. We use network calculus to derive the client's delay bound and incorporate it as a constraint in the Network Utility Maximization problem. We solve the resulting optimization using dual decomposition and obtain a semi-distributed TCP protocol that can be implemented with the help of SDN controller and the use of an Explicit Congestion Notification (ECN) bit. Additionally, we also propose a proactive approach for congestion control using digital twin. TCP Slice represents a significant step towards accommodating evolving internet traffic patterns and the need for better network management in the face of increasing application diversity. △ Less

Submitted 4 December, 2023; originally announced December 2023.

Auditing Yelp's Business Ranking and Review Recommendation Through the Lens of Fairness

Authors: Mohit Singhal, Javier Pacheco, Seyyed Mohammad Sadegh Moosavi Khorzooghi, Tanushree Debi, Abolfazl Asudeh, Gautam Das, Shirin Nilizadeh

Abstract: Auditing is critical to ensuring the fairness and reliability of decision-making systems. However, auditing a black-box system for bias can be challenging due to the lack of transparency in the model's internal workings. In many web applications, such as Yelp, it is challenging, if not impossible, to manipulate their inputs systematically to identify bias in the output. Yelp connects users and bus… ▽ More Auditing is critical to ensuring the fairness and reliability of decision-making systems. However, auditing a black-box system for bias can be challenging due to the lack of transparency in the model's internal workings. In many web applications, such as Yelp, it is challenging, if not impossible, to manipulate their inputs systematically to identify bias in the output. Yelp connects users and businesses, where users identify new businesses and simultaneously express their experiences through reviews. Yelp recommendation software moderates user-provided content by categorizing it into recommended and not-recommended sections. The recommended reviews, among other attributes, are used by Yelp's ranking algorithm to rank businesses in a neighborhood. Due to Yelp's substantial popularity and its high impact on local businesses' success, understanding the bias of its algorithms is crucial. This data-driven study, for the first time, investigates the bias of Yelp's business ranking and review recommendation system. We examine three hypotheses to assess if Yelp's recommendation software shows bias against reviews of less established users with fewer friends and reviews and if Yelp's business ranking algorithm shows bias against restaurants located in specific neighborhoods, particularly in hotspot regions, with specific demographic compositions. Our findings show that reviews of less-established users are disproportionately categorized as not-recommended. We also find a positive association between restaurants' location in hotspot regions and their average exposure. Furthermore, we observed some cases of severe disparity bias in cities where the hotspots are in neighborhoods with less demographic diversity or higher affluence and education levels. △ Less

Submitted 28 January, 2025; v1 submitted 4 August, 2023; originally announced August 2023.

Comments: To appear in the 19th International AAAI Conference on Web and Social Media (ICWSM 2025), please cite accordingly

AI-assisted Improved Service Provisioning for Low-latency XR over 5G NR

Authors: Moyukh Laha, Dibbendu Roy, Sourav Dutta, Goutam Das

Abstract: Extended Reality (XR) is one of the most important 5G/6G media applications that will fundamentally transform human interactions. However, ensuring low latency, high data rate, and reliability to support XR services poses significant challenges. This letter presents a novel AI-assisted service provisioning scheme that leverages predicted frames for processing rather than relying solely on actual f… ▽ More Extended Reality (XR) is one of the most important 5G/6G media applications that will fundamentally transform human interactions. However, ensuring low latency, high data rate, and reliability to support XR services poses significant challenges. This letter presents a novel AI-assisted service provisioning scheme that leverages predicted frames for processing rather than relying solely on actual frames. This method virtually increases the network delay budget and consequently improves service provisioning, albeit at the expense of minor prediction errors. The proposed scheme is validated by extensive simulations demonstrating a multi-fold increase in supported XR users and also provides crucial network design insights. △ Less

Submitted 18 July, 2023; originally announced July 2023.

Efficient Strongly Polynomial Algorithms for Quantile Regression

Authors: Suraj Shetiya, Shohedul Hasan, Abolfazl Asudeh, Gautam Das

Abstract: Linear Regression is a seminal technique in statistics and machine learning, where the objective is to build linear predictive models between a response (i.e., dependent) variable and one or more predictor (i.e., independent) variables. In this paper, we revisit the classical technique of Quantile Regression (QR), which is statistically a more robust alternative to the other classical technique of… ▽ More Linear Regression is a seminal technique in statistics and machine learning, where the objective is to build linear predictive models between a response (i.e., dependent) variable and one or more predictor (i.e., independent) variables. In this paper, we revisit the classical technique of Quantile Regression (QR), which is statistically a more robust alternative to the other classical technique of Ordinary Least Square Regression (OLS). However, while there exist efficient algorithms for OLS, almost all of the known results for QR are only weakly polynomial. Towards filling this gap, this paper proposes several efficient strongly polynomial algorithms for QR for various settings. For two dimensional QR, making a connection to the geometric concept of $k$-set, we propose an algorithm with a deterministic worst-case time complexity of $\mathcal{O}(n^{4/3} polylog(n))$ and an expected time complexity of $\mathcal{O}(n^{4/3})$ for the randomized version. We also propose a randomized divide-and-conquer algorithm -- RandomizedQR with an expected time complexity of $\mathcal{O}(n\log^2{(n)})$ for two dimensional QR problem. For the general case with more than two dimensions, our RandomizedQR algorithm has an expected time complexity of $\mathcal{O}(n^{d-1}\log^2{(n)})$. △ Less

Submitted 13 July, 2023; originally announced July 2023.

MABNet: Master Assistant Buddy Network with Hybrid Learning for Image Retrieval

Authors: Rohit Agarwal, Gyanendra Das, Saksham Aggarwal, Alexander Horsch, Dilip K. Prasad

Abstract: Image retrieval has garnered growing interest in recent times. The current approaches are either supervised or self-supervised. These methods do not exploit the benefits of hybrid learning using both supervision and self-supervision. We present a novel Master Assistant Buddy Network (MABNet) for image retrieval which incorporates both learning mechanisms. MABNet consists of master and assistant bl… ▽ More Image retrieval has garnered growing interest in recent times. The current approaches are either supervised or self-supervised. These methods do not exploit the benefits of hybrid learning using both supervision and self-supervision. We present a novel Master Assistant Buddy Network (MABNet) for image retrieval which incorporates both learning mechanisms. MABNet consists of master and assistant blocks, both learning independently through supervision and collectively via self-supervision. The master guides the assistant by providing its knowledge base as a reference for self-supervision and the assistant reports its knowledge back to the master by weight transfer. We perform extensive experiments on public datasets with and without post-processing. △ Less

Submitted 6 March, 2023; originally announced March 2023.

Comments: Accepted at International Conference on Acoustics, Speech, and Signal Processing (ICASSP) 2023

Learning cooperative behaviours in adversarial multi-agent systems

Authors: Ni Wang, Gautham P. Das, Alan G. Millard

Abstract: This work extends an existing virtual multi-agent platform called RoboSumo to create TripleSumo -- a platform for investigating multi-agent cooperative behaviors in continuous action spaces, with physical contact in an adversarial environment. In this paper we investigate a scenario in which two agents, namely `Bug' and `Ant', must team up and push another agent `Spider' out of the arena. To tackl… ▽ More This work extends an existing virtual multi-agent platform called RoboSumo to create TripleSumo -- a platform for investigating multi-agent cooperative behaviors in continuous action spaces, with physical contact in an adversarial environment. In this paper we investigate a scenario in which two agents, namely `Bug' and `Ant', must team up and push another agent `Spider' out of the arena. To tackle this goal, the newly added agent `Bug' is trained during an ongoing match between `Ant' and `Spider'. `Bug' must develop awareness of the other agents' actions, infer the strategy of both sides, and eventually learn an action policy to cooperate. The reinforcement learning algorithm Deep Deterministic Policy Gradient (DDPG) is implemented with a hybrid reward structure combining dense and sparse rewards. The cooperative behavior is quantitatively evaluated by the mean probability of winning the match and mean number of steps needed to win. △ Less

Submitted 10 February, 2023; originally announced February 2023.

Comments: 23rd Annual Conference, Towards Autonomous Robotic Systems 2022

Journal ref: Lecture Notes in Computer Science(), vol 13546. Springer, Cham. 2022

MAViC: Multimodal Active Learning for Video Captioning

Authors: Gyanendra Das, Xavier Thomas, Anant Raj, Vikram Gupta

Abstract: A large number of annotated video-caption pairs are required for training video captioning models, resulting in high annotation costs. Active learning can be instrumental in reducing these annotation requirements. However, active learning for video captioning is challenging because multiple semantically similar captions are valid for a video, resulting in high entropy outputs even for less-informa… ▽ More A large number of annotated video-caption pairs are required for training video captioning models, resulting in high annotation costs. Active learning can be instrumental in reducing these annotation requirements. However, active learning for video captioning is challenging because multiple semantically similar captions are valid for a video, resulting in high entropy outputs even for less-informative samples. Moreover, video captioning algorithms are multimodal in nature with a visual encoder and language decoder. Further, the sequential and combinatorial nature of the output makes the problem even more challenging. In this paper, we introduce MAViC which leverages our proposed Multimodal Semantics Aware Sequential Entropy (M-SASE) based acquisition function to address the challenges of active learning approaches for video captioning. Our approach integrates semantic similarity and uncertainty of both visual and language dimensions in the acquisition function. Our detailed experiments empirically demonstrate the efficacy of M-SASE for active learning for video captioning and improve on the baselines by a large margin. △ Less

Submitted 11 December, 2022; originally announced December 2022.

GPTs at Factify 2022: Prompt Aided Fact-Verification

Authors: Pawan Kumar Sahu, Saksham Aggarwal, Taneesh Gupta, Gyanendra Das

Abstract: One of the most pressing societal issues is the fight against false news. The false claims, as difficult as they are to expose, create a lot of damage. To tackle the problem, fact verification becomes crucial and thus has been a topic of interest among diverse research communities. Using only the textual form of data we propose our solution to the problem and achieve competitive results with other… ▽ More One of the most pressing societal issues is the fight against false news. The false claims, as difficult as they are to expose, create a lot of damage. To tackle the problem, fact verification becomes crucial and thus has been a topic of interest among diverse research communities. Using only the textual form of data we propose our solution to the problem and achieve competitive results with other approaches. We present our solution based on two approaches - PLM (pre-trained language model) based method and Prompt based method. The PLM-based approach uses the traditional supervised learning, where the model is trained to take 'x' as input and output prediction 'y' as P(y|x). Whereas, Prompt-based learning reflects the idea to design input to fit the model such that the original objective may be re-framed as a problem of (masked) language modeling. We may further stimulate the rich knowledge provided by PLMs to better serve downstream tasks by employing extra prompts to fine-tune PLMs. Our experiments showed that the proposed method performs better than just fine-tuning PLMs. We achieved an F1 score of 0.6946 on the FACTIFY dataset and a 7th position on the competition leader-board. △ Less

Submitted 29 June, 2022; originally announced June 2022.

Comments: Accepted in AAAI'22: First Workshop on Multimodal Fact-Checking and Hate Speech Detection, Februrary 22 - March 1, 2022,Vancouver, BC, Canada

Skyrmion-Magnetic Tunnel Junction Synapse with Mixed Synaptic Plasticity for Neuromorphic Computing

Authors: Aijaz H. Lone, Arnab Ganguly, Selma Amara, Gobind Das, H. Fariborzi

Abstract: Magnetic skyrmion-based data storage and unconventional computing devices have gained increasing attention due to their topological protection, small size, and low driving current. However, skyrmion creation, deletion, and motion are still being studied. In this study, we propose a skyrmion-based neuromorphic magnetic tunnel junction (MTJ) device with both long- and short-term plasticity (LTP and… ▽ More Magnetic skyrmion-based data storage and unconventional computing devices have gained increasing attention due to their topological protection, small size, and low driving current. However, skyrmion creation, deletion, and motion are still being studied. In this study, we propose a skyrmion-based neuromorphic magnetic tunnel junction (MTJ) device with both long- and short-term plasticity (LTP and STP) (mixed synaptic plasticity). We showed that plasticity could be controlled by magnetic field, spin-orbit torque (SOT), and the voltage-controlled magnetic anisotropy (VCMA) switching mechanism. LTP depends on the skyrmion density and is manipulated by the SOT and magnetic field while STP is controlled by the VCMA. The LTP property of the device was utilized for static image recognition. By incorporating the STP feature, the device gained additional temporal filtering ability and could adapt to a dynamic environment. The skyrmions were conserved and confined to a nanotrack to minimize the skyrmion nucleation energy. The synapse device was trained and tested for emulating a deep neural network. We observed that when the skyrmion density was increased, the inference accuracy improved: 90% accuracy was achieved by the system at the highest density. We further demonstrated the dynamic environment learning and inference capabilities of the proposed device. △ Less

Submitted 30 May, 2022; originally announced May 2022.

Comments: Submitted to Physical Review Applied

CCOMPASSION: A Hybrid Cloudlet Placement Framework over Passive Optical Access Networks

Authors: Sourav Mondal, Goutam Das, Elaine Wong

Abstract: Cloud-based computing technology is one of the most significant technical advents of the last decade and extension of this facility towards access networks by aggregation of cloudlets is a step further. To fulfill the ravenous demand for computational resources entangled with the stringent latency requirements of computationally-heavy applications related to augmented reality, cognitive assistance… ▽ More Cloud-based computing technology is one of the most significant technical advents of the last decade and extension of this facility towards access networks by aggregation of cloudlets is a step further. To fulfill the ravenous demand for computational resources entangled with the stringent latency requirements of computationally-heavy applications related to augmented reality, cognitive assistance and context-aware computation, installation of cloudlets near the access segment is a very promising solution because of its support for wide geographical network distribution, low latency, mobility and heterogeneity. In this paper, we propose a novel framework, Cloudlet Cost OptiMization over PASSIve Optical Network (CCOMPASSION), and formulate a nonlinear mixed-integer program to identify optimal cloudlet placement locations such that installation cost is minimized whilst meeting the capacity and latency constraints. Considering urban, suburban and rural scenarios as commonly-used network deployment models, we investigate the feasibility of the proposed model over them and provide guidance on the overall cloudlet facility installation over optical access network. We also study the percentage of incremental energy budget in the presence of cloudlets of the existing network. The final results from our proposed model can be considered as fundamental cornerstones for network planning with hybrid cloudlet network architectures. △ Less

Submitted 25 February, 2022; originally announced February 2022.

Comments: This paper is published in 2018 IEEE Conference on Computer Communications (INFOCOM). Copyright @ IEEE

Report number: 18150397

Journal ref: IEEE INFOCOM 2018 - IEEE Conference on Computer Communications

Deep Learning based Coverage and Rate Manifold Estimation in Cellular Networks

Authors: Washim Uddin Mondal, Praful D. Mankar, Goutam Das, Vaneet Aggarwal, Satish V. Ukkusuri

Abstract: This article proposes Convolutional Neural Network-based Auto Encoder (CNN-AE) to predict location-dependent rate and coverage probability of a network from its topology. We train the CNN utilising BS location data of India, Brazil, Germany, and the USA and compare its performance with stochastic geometry (SG) based analytical models. In comparison to the best-fitted SG-based model, CNN-AE improve… ▽ More This article proposes Convolutional Neural Network-based Auto Encoder (CNN-AE) to predict location-dependent rate and coverage probability of a network from its topology. We train the CNN utilising BS location data of India, Brazil, Germany, and the USA and compare its performance with stochastic geometry (SG) based analytical models. In comparison to the best-fitted SG-based model, CNN-AE improves the coverage and rate prediction errors by a margin of as large as $40\%$ and $25\%$ respectively. As an application, we propose a low complexity, provably convergent algorithm that, using trained CNN-AE, can compute locations of new BSs that need to be deployed in a network in order to satisfy pre-defined spatially heterogeneous performance goals. △ Less

Submitted 21 August, 2022; v1 submitted 13 February, 2022; originally announced February 2022.

Journal ref: IEEE Transactions on Cognitive Communications and Networking, 2022

Robust QoT Assured Resource Allocation in Shared Backup Path Protection Based EONs

Authors: Venkatesh Chebolu, Sadananda Behera, Goutam Das

Abstract: Survivability is mission-critical for elastic optical networks (EONs) as they are expected to carry an enormous amount of data. In this paper, we consider the problem of designing shared backup path protection (SBPP) based EON that facilitates the minimum quality-of-transmission (QoT) assured allocation against physical layer impairments (PLIs) under any single link/shared risk link group (SRLG) f… ▽ More Survivability is mission-critical for elastic optical networks (EONs) as they are expected to carry an enormous amount of data. In this paper, we consider the problem of designing shared backup path protection (SBPP) based EON that facilitates the minimum quality-of-transmission (QoT) assured allocation against physical layer impairments (PLIs) under any single link/shared risk link group (SRLG) failure for static and dynamic traffic scenarios. In general, the effect of PLIs on lightpath varies based on the location of failure of a link as it introduces different active working and backup paths. To address these issues in the design of SBPP EON, we formulate a mixed integer linear programming (MILP) based robust optimization framework for static traffic with the objective of minimizing overall fragmentation. In this process, we use the efficient bitloading technique for spectrum allocation for the first time in survivable EONs. In addition, we propose a novel SBPP-impairment aware (SBPP-IA) algorithm considering the limitations of MILP for larger networks. For this purpose, we introduce a novel sorting technique named most congested working-least congested backup first (MCW-LCBF) to sort the given set of static requests. Next, we employ our SBPP-IA algorithm for dynamic traffic scenario and compare it with existing algorithms in terms of different QoT parameters. We demonstrated through simulations that our study provides around 40% more QoT guaranteed requests compared to existing ones. △ Less

Submitted 13 January, 2022; originally announced January 2022.

Online Slice Reconfiguration for End-to-End QoE in 6G Applications

Authors: Dibbendu Roy, Aravinda S. Rao, Tansu Alpcan, Akilan Wick, Goutam Das, Marimuthu Palaniswami

Abstract: End-to-end (E2E) quality of experience (QoE) for 6G applications depends on the synchronous allocation of networking and computing resources, also known as slicing. However, the relationship between the resources and the E2E QoE outcomes is typically stochastic and non-stationary. Existing works consider known resource demands for slicing and formulate optimization problems for slice reconfigurati… ▽ More End-to-end (E2E) quality of experience (QoE) for 6G applications depends on the synchronous allocation of networking and computing resources, also known as slicing. However, the relationship between the resources and the E2E QoE outcomes is typically stochastic and non-stationary. Existing works consider known resource demands for slicing and formulate optimization problems for slice reconfiguration. In this work, we create and manage slices by learning the relationship between E2E QoE and resources. We develop a gradient-based online slice reconfiguration algorithm (OSRA) to reconfigure and manage slices in resource-constrained scenarios for radio access networks (RAN). We observe that our methodology meets the QoE requirements with high accuracy compared to existing approaches. It improves upon the existing approaches by approximately 98\% for bursty traffic variations. Our algorithm has fast convergence and achieves low E2E delay violations for lower priority slices. △ Less

Submitted 13 January, 2022; originally announced January 2022.

Achieving AI-enabled Robust End-to-End Quality of Experience over Radio Access Networks

Authors: Dibbendu Roy, Aravinda S. Rao, Tansu Alpcan, Goutam Das, Marimuthu Palaniswami

Abstract: Emerging applications such as Augmented Reality, the Internet of Vehicles and Remote Surgery require both computing and networking functions working in harmony. The End-to-end (E2E) quality of experience (QoE) for these applications depends on the synchronous allocation of networking and computing resources. However, the relationship between the resources and the E2E QoE outcomes is typically stoc… ▽ More Emerging applications such as Augmented Reality, the Internet of Vehicles and Remote Surgery require both computing and networking functions working in harmony. The End-to-end (E2E) quality of experience (QoE) for these applications depends on the synchronous allocation of networking and computing resources. However, the relationship between the resources and the E2E QoE outcomes is typically stochastic and non-linear. In order to make efficient resource allocation decisions, it is essential to model these relationships. This article presents a novel machine-learning based approach to learn these relationships and concurrently orchestrate both resources for this purpose. The machine learning models further help make robust allocation decisions regarding stochastic variations and simplify robust optimization to a conventional constrained optimization. When resources are insufficient to accommodate all application requirements, our framework supports executing some of the applications with minimal degradation (graceful degradation) of E2E QoE. We also show how we can implement the learning and optimization methods in a distributed fashion by the Software-Defined Network (SDN) and Kubernetes technologies. Our results show that deep learning-based modelling achieves E2E QoE with approximately 99.8\% accuracy, and our robust joint-optimization technique allocates resources efficiently when compared to existing differential services alternatives. △ Less

Submitted 13 January, 2022; originally announced January 2022.

Roman Domination in Convex Bipartite Graphs

Authors: Sasmita Rout, Gautam K. Das

Abstract: In the Roman domination problem, an undirected simple graph $G(V,E)$ is given. The objective of Roman domination problem is to find a function $f:V\rightarrow {\{0,1,2\}}$ such that for any vertex $v\in V$ with $f(v)=0$ must be adjacent to at least one vertex $u\in V$ with $f(u)=2$ and $\sum_{u\in V} f(u)$, called Roman domination number, is minimized. It is already proven that the Roman dominatio… ▽ More In the Roman domination problem, an undirected simple graph $G(V,E)$ is given. The objective of Roman domination problem is to find a function $f:V\rightarrow {\{0,1,2\}}$ such that for any vertex $v\in V$ with $f(v)=0$ must be adjacent to at least one vertex $u\in V$ with $f(u)=2$ and $\sum_{u\in V} f(u)$, called Roman domination number, is minimized. It is already proven that the Roman domination problem (RDP) is NP-complete for general graphs and it remains NP-complete for bipartite graphs. In this paper, we propose a dynamic programming based polynomial time algorithm for RDP in convex bipartite graph. △ Less

Submitted 17 November, 2021; originally announced November 2021.

Viewing citation trend of Indian physics and astronomy research papers since 2005 through the lens of some new indicators

Authors: Gopinath Das, Bidyarthi Dutta, Anup Kumar Das

Abstract: The indicator Citation Swing Factor (CSF) has recently been developed to measure this diffusion process quantitatively on the basis of h-core citations, excess citations and total citations. The observed or experimental value of CSF as followed from the basic definition is (dθ/dε), which resulted (-R3/he2) based on a theoretical calculation, where R2, h2 and e2 indicate total citations, h-core cit… ▽ More The indicator Citation Swing Factor (CSF) has recently been developed to measure this diffusion process quantitatively on the basis of h-core citations, excess citations and total citations. The observed or experimental value of CSF as followed from the basic definition is (dθ/dε), which resulted (-R3/he2) based on a theoretical calculation, where R2, h2 and e2 indicate total citations, h-core citations and excess citations respectively. The later expression indicates the expected or theoretical value of CSF. This paper found out (dθ/dε) for Indian physics research output appeared in selective Indian journals since 2005 to 2020 and compared it with the respective theoretical values. The average error over entire time span is found 2.26% indicating close proximity between theoretically expected and practically observed values. Besides, three other scientometric indicators are introduced here, viz. Time-Normalised Total Cited Ratio (TC), Time-Normalised Cited Uncited Ratio (CU) and Time-Normalised Total Uncited Ratio (TU). The numerical values of these indicators are found out for the same sample and the temporal variations along with their mutual interrelationships are determined by regression analysis. △ Less

Submitted 11 September, 2021; originally announced September 2021.

Comments: 9 pages, 3 figures

Achieving QoS for Real-Time Bursty Applications over Passive Optical Networks

Authors: Dibbendu Roy, Aravinda S. Rao, Tansu Alpcan, Goutam Das, Marimuthu Palaniswami

Abstract: Emerging real-time applications such as those classified under ultra-reliable low latency (uRLLC) generate bursty traffic and have strict Quality of Service (QoS) requirements. Passive Optical Network (PON) is a popular access network technology, which is envisioned to handle such applications at the access segment of the network. However, the existing standards cannot handle strict QoS constraint… ▽ More Emerging real-time applications such as those classified under ultra-reliable low latency (uRLLC) generate bursty traffic and have strict Quality of Service (QoS) requirements. Passive Optical Network (PON) is a popular access network technology, which is envisioned to handle such applications at the access segment of the network. However, the existing standards cannot handle strict QoS constraints. The available solutions rely on instantaneous heuristic decisions and maintain QoS constraints (mostly bandwidth) in an average sense. Existing works with optimal strategies are computationally complex and are not suitable for uRLLC applications. This paper presents a novel computationally-efficient, far-sighted bandwidth allocation policy design for facilitating bursty traffic in a PON framework while satisfying strict QoS (age of information/delay and bandwidth) requirements of modern applications. To this purpose, first we design a delay-tracking mechanism which allows us to model the resource allocation problem from a control-theoretic viewpoint as a Model Predictive Control (MPC). MPC helps in taking far-sighted decisions regarding resource allocations and captures the time-varying dynamics of the network. We provide computationally efficient polynomial-time solutions and show its implementation in the PON framework. Compared to existing approaches, MPC reduces delay violations by approximately 15% for a delay-constrained application of 1ms target. Our approach is also robust to varying traffic arrivals. △ Less

Submitted 5 September, 2021; originally announced September 2021.

Adaptive Rate NOMA for Cellular IoT Networks

Authors: G. Sreya, S. Saigadha, Praful D. Mankar, Goutam Das, Harpreet S. Dhillon

Abstract: Internet-of-Things (IoT) technology is envisioned to enable a variety of real-time applications by interconnecting billions of sensors/devices deployed to observe some random physical processes. These IoT devices rely on low-power wide-area wireless connectivity for transmitting, mostly fixed- but small-size, status updates of their associated random processes. The cellular networks are seen as a… ▽ More Internet-of-Things (IoT) technology is envisioned to enable a variety of real-time applications by interconnecting billions of sensors/devices deployed to observe some random physical processes. These IoT devices rely on low-power wide-area wireless connectivity for transmitting, mostly fixed- but small-size, status updates of their associated random processes. The cellular networks are seen as a natural candidate for providing reliable wireless connectivity to IoT devices. However, the conventional orthogonal multiple access (OMA) to these massive number of devices is expected to degrade the spectral efficiency. As a promising alternative to OMA, the cellular base stations (BSs) can employ non-orthogonal multiple access (NOMA) for the uplink transmissions of mobile users and IoT devices. In particular, the uplink NOMA can be configured such that the mobile user can adapt transmission rate based on its channel condition while the IoT device transmits at a fixed rate. For this setting, we analyze the ergodic capacity of mobile users and the mean local delay of IoT devices using stochastic geometry. Our analysis demonstrates that the above NOMA configuration can provide better ergodic capacity for mobile users compare to OMA when IoT devices' delay constraint is strict. Furthermore, we also show that NOMA can support a larger packet size for IoT devices than OMA under the same delay constraint. △ Less

Submitted 3 December, 2021; v1 submitted 18 August, 2021; originally announced August 2021.

Approximation Algorithms For The Dispersion Problems in a Metric Space

Authors: Pawan K. Mishra, Gautam K. Das

Abstract: In this article, we consider the $c$-dispersion problem in a metric space $(X,d)$. Let $P=\{p_{1}, p_{2}, \ldots, p_{n}\}$ be a set of $n$ points in a metric space $(X,d)$. For each point $p \in P$ and $S \subseteq P$, we define $cost_{c}(p,S)$ as the sum of distances from $p$ to the nearest $c $ points in $S \setminus \{p\}$, where $c\geq 1$ is a fixed integer. We define… ▽ More In this article, we consider the $c$-dispersion problem in a metric space $(X,d)$. Let $P=\{p_{1}, p_{2}, \ldots, p_{n}\}$ be a set of $n$ points in a metric space $(X,d)$. For each point $p \in P$ and $S \subseteq P$, we define $cost_{c}(p,S)$ as the sum of distances from $p$ to the nearest $c $ points in $S \setminus \{p\}$, where $c\geq 1$ is a fixed integer. We define $cost_{c}(S)=\min_{p \in S}\{cost_{c}(p,S)\}$ for $S \subseteq P$. In the $c$-dispersion problem, a set $P$ of $n$ points in a metric space $(X,d)$ and a positive integer $k \in [c+1,n]$ are given. The objective is to find a subset $S\subseteq P$ of size $k$ such that $cost_{c}(S)$ is maximized. We propose a simple polynomial time greedy algorithm that produces a $2c$-factor approximation result for the $c$-dispersion problem in a metric space. The best known result for the $c$-dispersion problem in the Euclidean metric space $(X,d)$ is $2c^2$, where $P \subseteq \mathbb{R}^2$ and the distance function is Euclidean distance [ Amano, K. and Nakano, S. I., Away from Rivals, CCCG, pp.68-71, 2018 ]. We also prove that the $c$-dispersion problem in a metric space is $W[1]$-hard. △ Less

Submitted 9 June, 2021; v1 submitted 19 May, 2021; originally announced May 2021.

Comments: 9. arXiv admin note: text overlap with arXiv:2105.09217

Approximation Algorithms For The Euclidean Dispersion Problems

Authors: Pawan K. Mishra, Gautam K. Das

Abstract: In this article, we consider the Euclidean dispersion problems. Let $P=\{p_{1}, p_{2}, \ldots, p_{n}\}$ be a set of $n$ points in $\mathbb{R}^2$. For each point $p \in P$ and $S \subseteq P$, we define $cost_γ(p,S)$ as the sum of Euclidean distance from $p$ to the nearest $γ$ point in $S \setminus \{p\}$. We define $cost_γ(S)=\min_{p \in S}\{cost_γ(p,S)\}$ for $S \subseteq P$. In the $γ$-dispersio… ▽ More In this article, we consider the Euclidean dispersion problems. Let $P=\{p_{1}, p_{2}, \ldots, p_{n}\}$ be a set of $n$ points in $\mathbb{R}^2$. For each point $p \in P$ and $S \subseteq P$, we define $cost_γ(p,S)$ as the sum of Euclidean distance from $p$ to the nearest $γ$ point in $S \setminus \{p\}$. We define $cost_γ(S)=\min_{p \in S}\{cost_γ(p,S)\}$ for $S \subseteq P$. In the $γ$-dispersion problem, a set $P$ of $n$ points in $\mathbb{R}^2$ and a positive integer $k \in [γ+1,n]$ are given. The objective is to find a subset $S\subseteq P$ of size $k$ such that $cost_γ(S)$ is maximized. We consider both $2$-dispersion and $1$-dispersion problem in $\mathbb{R}^2$. Along with these, we also consider $2$-dispersion problem when points are placed on a line. In this paper, we propose a simple polynomial time $(2\sqrt 3 + ε)$-factor approximation algorithm for the $2$-dispersion problem, for any $ε> 0$, which is an improvement over the best known approximation factor $4\sqrt3$ [Amano, K. and Nakano, S. I., An approximation algorithm for the $2$-dispersion problem, IEICE Transactions on Information and Systems, Vol. 103(3), pp. 506-508, 2020]. Next, we develop a common framework for designing an approximation algorithm for the Euclidean dispersion problem. With this common framework, we improve the approximation factor to $2\sqrt 3$ for the $2$-dispersion problem in $\mathbb{R}^2$. Using the same framework, we propose a polynomial time algorithm, which returns an optimal solution for the $2$-dispersion problem when points are placed on a line. Moreover, to show the effectiveness of the framework, we also propose a $2$-factor approximation algorithm for the $1$-dispersion problem in $\mathbb{R}^2$. △ Less

Submitted 19 May, 2021; originally announced May 2021.

Comments: 17

Learning Aided Auctioning based Spectrum Access System in a Wireless Optical Network

Authors: Atri Mukhopadhyay, Goutam Das

Abstract: This paper focusses on Service Level Agreement (SLA) based end-to-end Quality of Service (QoS) maintenance across a wireless optical integrated network. We use long term evolution (LTE) based spectrum access system (SAS) in the wireless network and the optical network is comprised of an Ethernet Passive Optical Network (EPON). The proposal targets a learning-based intelligent SAS where opportunist… ▽ More This paper focusses on Service Level Agreement (SLA) based end-to-end Quality of Service (QoS) maintenance across a wireless optical integrated network. We use long term evolution (LTE) based spectrum access system (SAS) in the wireless network and the optical network is comprised of an Ethernet Passive Optical Network (EPON). The proposal targets a learning-based intelligent SAS where opportunistic allocation of any available bandwidth is done after meeting the SLA requirements. Such an opportunistic allocation is particularly beneficial for nomadic users with varying QoS requirements. The opportunistic allocation is carried out with the help of Vickrey-Clarke-Groves (VCG) auction. The proposal allows the users of the integrated network to decide the payment they want to make in order to opportunistically avail bandwidth. Learning automata is used for the users to intelligently converge to the optimal payment value based on the network load. The payment made by the users is later used by the optical network units of the EPON to prepare the bids for the auction. The proposal has been verified through extensive simulations. △ Less

Submitted 30 November, 2021; v1 submitted 25 April, 2021; originally announced April 2021.

Comments: Communicated to IEEE for possible publication

Queuing Analysis of Opportunistic Cognitive Radio IoT Network with Imperfect Sensing

Authors: Asif Ahmed Sardar, Dibbendu Roy, Washim Uddin Mondal, Goutam Das

Abstract: In this paper, we analyze a Cognitive Radio-based Internet-of-Things (CR-IoT) network comprising a Primary Network Provider (PNP) and an IoT operator. The PNP uses its licensed spectrum to serve its users. The IoT operator identifies the white-space in the licensed band at regular intervals and opportunistically exploits them to serve the IoT nodes under its coverage. IoT nodes are battery-operate… ▽ More In this paper, we analyze a Cognitive Radio-based Internet-of-Things (CR-IoT) network comprising a Primary Network Provider (PNP) and an IoT operator. The PNP uses its licensed spectrum to serve its users. The IoT operator identifies the white-space in the licensed band at regular intervals and opportunistically exploits them to serve the IoT nodes under its coverage. IoT nodes are battery-operated devices that require periodical energy replenishment. We employ the Microwave Power Transfer (MPT) technique for its superior energy transfer efficiency over long-distance. The white-space detection process is not always perfect and the IoT operator may jeopardize the PNP's transmissions due to misdetection. To reduce the possibility of such interferences, some of the spectrum holes must remain unutilized, even when the IoT nodes have data to transmit. The IoT operator needs to decide what percentage of the white-space to keep unutilized and how to judiciously use the rest for data transmission and energy-replenishment to maintain an optimal balance between the average interference inflicted on PNP's users and the Quality-of-Service (QoS) experienced by IoT nodes. Due to the periodic nature of the spectrum-sensing process, Discrete Time Markov Chain (DTMC) method can realistically model this framework. In literature, activities of the PNP and IoT operator are assumed to be mutually exclusive, for ease of analysis. Our model incorporates possible overlaps between these activities, making the analysis more realistic. Using our model, the sustainability region of the CR-IoT network can be obtained. The accuracy of our analysis is demonstrated via extensive simulation. △ Less

Submitted 16 March, 2021; originally announced March 2021.

Total Domination in Unit Disk Graphs

Authors: Sangram K. Jena, Gautam K. Das

Abstract: Let $G=(V,E)$ be an undirected graph. We call $D_t \subseteq V$ as a total dominating set (TDS) of $G$ if each vertex $v \in V$ has a dominator in $D$ other than itself. Here we consider the TDS problem in unit disk graphs, where the objective is to find a minimum cardinality total dominating set for an input graph. We prove that the TDS problem is NP-hard in unit disk graphs. Next, we propose an… ▽ More Let $G=(V,E)$ be an undirected graph. We call $D_t \subseteq V$ as a total dominating set (TDS) of $G$ if each vertex $v \in V$ has a dominator in $D$ other than itself. Here we consider the TDS problem in unit disk graphs, where the objective is to find a minimum cardinality total dominating set for an input graph. We prove that the TDS problem is NP-hard in unit disk graphs. Next, we propose an 8-factor approximation algorithm for the problem. The running time of the proposed approximation algorithm is $O(n \log k)$, where $n$ is the number of vertices of the input graph and $k$ is output size. We also show that TDS problem admits a PTAS in unit disk graphs. △ Less

Submitted 23 July, 2020; originally announced July 2020.

On Exact Distribution of Poisson-Voronoi Area in $K$-tier HetNets with Generalized Association Rule

Authors: Washim Uddin Mondal, Goutam Das

Abstract: This letter characterizes the exact distribution function of a typical Voronoi area in a $K$-tier Poisson network. The users obey a generalized association (GA) rule, which is a superset of nearest base station association and maximum received power based association (with arbitrary fading) rules that are commonly adopted in the literature. Combining the Robbins' theorem and the probability genera… ▽ More This letter characterizes the exact distribution function of a typical Voronoi area in a $K$-tier Poisson network. The users obey a generalized association (GA) rule, which is a superset of nearest base station association and maximum received power based association (with arbitrary fading) rules that are commonly adopted in the literature. Combining the Robbins' theorem and the probability generating functional of a Poisson point process, we obtain the exact moments of a typical $k$-th tier Voronoi area, $k \in \{1,...,K\}$ under the GA rule. We apply this result in several special cases. For example, we prove that in multi-tier networks with the GA rule, the mean of $k$-th tier Voronoi area can exactly be expressed in a closed-form. We also obtain simplified expressions of its higher-order moments for both average and instantaneous received power based user association. In single-tier networks with exponential fading, the later association rule provides closed-form expression of the second-order moment of a typical Voronoi area. We numerically evaluate this exact expression and compare it with an approximated result. △ Less

Submitted 1 July, 2020; originally announced July 2020.

Journal ref: IEEE Communications Letters, 2020

The Generalized Independent and Dominating Set Problems on Unit Disk Graphs

Authors: Sangram K. Jena, Ramesh K. Jallu, Gautam K. Das, Subhas C. Nandy

Abstract: In this article, we study a generalized version of the maximum independent set and minimum dominating set problems, namely, the maximum $d$-distance independent set problem and the minimum $d$-distance dominating set problem on unit disk graphs for a positive integer $d>0$. We first show that the maximum $d$-distance independent set problem and the minimum $d$-distance dominating set problem belon… ▽ More In this article, we study a generalized version of the maximum independent set and minimum dominating set problems, namely, the maximum $d$-distance independent set problem and the minimum $d$-distance dominating set problem on unit disk graphs for a positive integer $d>0$. We first show that the maximum $d$-distance independent set problem and the minimum $d$-distance dominating set problem belongs to NP-hard class. Next, we propose a simple polynomial-time constant-factor approximation algorithms and PTAS for both the problems. △ Less

Submitted 27 June, 2020; originally announced June 2020.

Centralized and Decentralized Non-Cooperative Load-Balancing Games among Federated Cloudlets

Authors: Sourav Mondal, Goutam Das, Elaine Wong

Abstract: Edge computing servers like cloudlets from different service providers compensate scarce computational, memory, and energy resources of mobile devices, are distributed across access networks. However, depending on the mobility pattern and dynamically varying computational requirements of associated mobile devices, cloudlets at different parts of the network become either overloaded or under-loaded… ▽ More Edge computing servers like cloudlets from different service providers compensate scarce computational, memory, and energy resources of mobile devices, are distributed across access networks. However, depending on the mobility pattern and dynamically varying computational requirements of associated mobile devices, cloudlets at different parts of the network become either overloaded or under-loaded. Hence, load balancing among neighboring cloudlets appears to be an essential research problem. Nonetheless, the existing load balancing frameworks are unsuitable for low-latency applications. Thus, in this paper, we propose an economic and non-cooperative load balancing game for low-latency applications among federated neighboring cloudlets from the same as well as different service providers and heterogeneous classes of job requests. Firstly, we propose a centralized incentive mechanism to compute the pure strategy Nash equilibrium load balancing strategies of the cloudlets under the supervision of a neutral mediator. With this mechanism, we ensure that the truthful revelation of private information to the mediator is a weakly-dominant strategy for all the federated cloudlets. Secondly, we propose a continuous-action reinforcement learning automata-based algorithm, which allows each cloudlet to independently compute the Nash equilibrium in a completely distributed network setting. We critically study the convergence properties of the designed learning algorithm, scaffolding our understanding of the underlying load balancing game for faster convergence. Furthermore, through extensive simulations, we study the impacts of exploration and exploitation on learning accuracy. This is the first study to show the effectiveness of reinforcement learning algorithms for load balancing games among neighboring cloudlets. △ Less

Submitted 5 May, 2021; v1 submitted 30 May, 2020; originally announced June 2020.

Report number: 108847

Liar's Domination in Unit Disk Graphs

Authors: Ramesh K. Jallu, Sangram K. Jena, Gautam K. Das

Abstract: In this article, we study a variant of the minimum dominating set problem known as the minimum liar's dominating set (MLDS) problem. We prove that the MLDS problem is NP-hard in unit disk graphs. Next, we show that the recent sub-quadratic time $\frac{11}{2}$-factor approximation algorithm \cite{bhore} for the MLDS problem is erroneous and propose a simple $O(n + m)$ time 7.31-factor approximation… ▽ More In this article, we study a variant of the minimum dominating set problem known as the minimum liar's dominating set (MLDS) problem. We prove that the MLDS problem is NP-hard in unit disk graphs. Next, we show that the recent sub-quadratic time $\frac{11}{2}$-factor approximation algorithm \cite{bhore} for the MLDS problem is erroneous and propose a simple $O(n + m)$ time 7.31-factor approximation algorithm, where $n$ and $m$ are the number of vertices and edges in the input unit disk graph, respectively. Finally, we prove that the MLDS problem admits a polynomial-time approximation scheme. △ Less

Submitted 28 May, 2020; originally announced May 2020.

Protocol design for energy efficient OLT transmitter in TWDM-PON guaranteeing SLA of up-stream and down-stream traffic

Authors: Sourav Dutta, Dibbendu Roy, Goutam Das

Abstract: Environmental and economic concerns promote research on designing energy-efficient Time and Wavelength Division Multiplexed Ethernet Passive Optical Network (TWDM-EPON), which is the future extension to TDM-EPON. In TDM-EPON, a plethora of research is already present to achieve energy savings at Optical Network Units (ONUs) which can easily be applied for TWDM-EPON ONUs. However, TWDM-EPON provide… ▽ More Environmental and economic concerns promote research on designing energy-efficient Time and Wavelength Division Multiplexed Ethernet Passive Optical Network (TWDM-EPON), which is the future extension to TDM-EPON. In TDM-EPON, a plethora of research is already present to achieve energy savings at Optical Network Units (ONUs) which can easily be applied for TWDM-EPON ONUs. However, TWDM-EPON provides an additional opportunity for saving energy at the Optical Line Terminal (OLT). All existing protocols have primarily been designed for saving energy at the OLT receivers. The protocols to save energy at the OLT receives depends only on the Up-Stream(US) traffic scheduling while its transmitter counterpart depends on both US and Down-Stream (DS) scheduling since the OLT transmits GATE message along with DS traffic. The US and DS scheduling have a basic difference. The MAC protocol doesn't allow scheduling of US traffic of an ONU after its REPORT arrival at multiple disjoint time slots. However, this restriction is absent for DS traffic and hence, the grant-size of an ONU can be partitioned and every part can be scheduled at different times. In this paper, we propose a method for saving energy at the OLT transmitters in TWDM-EPON while satisfying the SLAs. This includes a heuristic algorithm to partition the DS grant and schedule them. Through extensive simulations, we demonstrate that the proposed method provides a significant improvement in energy efficiency as compared to existing protocols (up to 45%). △ Less

Submitted 24 September, 2019; originally announced September 2019.

On $d$-distance $m$-tuple ($\ell, r$)-domination in graphs

Authors: Sangram K. Jena, Ramesh K. Jallu, Gautam K. Das

Abstract: In this article, we study the $d$-distance $m$-tuple ($\ell, r$)-domination problem. Given a simple undirected graph $G=(V, E)$, and positive integers $d, m, \ell$ and $r$, a subset $V' \subseteq V$ is said to be a $d$-distance $m$-tuple ($\ell, r$)-dominating set if it satisfies the following conditions: (i) each vertex $v \in V$ is $d$-distance dominated by at least $m$ vertices in $V'$, and (ii… ▽ More In this article, we study the $d$-distance $m$-tuple ($\ell, r$)-domination problem. Given a simple undirected graph $G=(V, E)$, and positive integers $d, m, \ell$ and $r$, a subset $V' \subseteq V$ is said to be a $d$-distance $m$-tuple ($\ell, r$)-dominating set if it satisfies the following conditions: (i) each vertex $v \in V$ is $d$-distance dominated by at least $m$ vertices in $V'$, and (ii) each $r$ size subset $U$ of $V$ is $d$-distance dominated by at least $\ell$ vertices in $V'$. Here, a vertex $v$ is $d$-distance dominated by another vertex $u$ means the shortest path distance between $u$ and $v$ is at most $d$ in $G$. A set $U$ is $d$-distance dominated by a set of $\ell$ vertices means size of the union of the $d$-distance neighborhood of all vertices of $U$ in $V'$ is at least $\ell$. The objective of the $d$-distance $m$-tuple ($\ell, r$)-domination problem is to find a minimum size subset $V' \subseteq V$ satisfying the above two conditions. We prove that the problem of deciding whether a graph $G$ has (i) a 1-distance $m$-tuple ($\ell, r$)-dominating set for each fixed value of $m, \ell$, and $r$, and (ii) a $d$-distance $m$-tuple ($\ell, 2$)-dominating set for each fixed value of $d (> 1), m$, and $\ell$ of cardinality at most $k$ (here $k$ is a positive integer) are NP-complete. We also prove that for any $\varepsilon>0$, the 1-distance $m$-tuple $(\ell, r)$-domination problem and the $d$-distance $m$-tuple $(\ell,2)$-domination problem cannot be approximated within a factor of $(\frac{1}{2}- \varepsilon)\ln |V|$ and $(\frac{1}{4}- \varepsilon)\ln |V|$, respectively, unless $P = NP$. △ Less

Submitted 19 April, 2021; v1 submitted 26 July, 2019; originally announced July 2019.

Buffer-aided Resource Allocation for a Price Based Opportunistic Cognitive Radio Network

Authors: Nilanjan Biswas, Goutam Das, Priyadip Ray

Abstract: In this paper, a resource allocation problem for an opportunistic cooperative cognitive radio network is considered, where cognitive radio nodes send their hard decisions to the fusion center. The fusion center plays dual role, i.e., takes the global decision (i.e., decision about the primary user's activity) as well as allocates transmission time durations among cognitive radio nodes. Revenue bas… ▽ More In this paper, a resource allocation problem for an opportunistic cooperative cognitive radio network is considered, where cognitive radio nodes send their hard decisions to the fusion center. The fusion center plays dual role, i.e., takes the global decision (i.e., decision about the primary user's activity) as well as allocates transmission time durations among cognitive radio nodes. Revenue based utility functions are considered at the fusion center and cognitive radio nodes. An optimization problem is formulated to maximize the fusion center's revenue while satisfying some well defined constraints. User selection among cognitive radio nodes is performed in order to make the optimization problem feasible. △ Less

Submitted 17 May, 2019; originally announced May 2019.

Comments: 32 pages, 8 figures, Journal

Approximate Query Processing using Deep Generative Models

Authors: Saravanan Thirumuruganathan, Shohedul Hasan, Nick Koudas, Gautam Das

Abstract: Data is generated at an unprecedented rate surpassing our ability to analyze them. The database community has pioneered many novel techniques for Approximate Query Processing (AQP) that could give approximate results in a fraction of time needed for computing exact results. In this work, we explore the usage of deep learning (DL) for answering aggregate queries specifically for interactive applica… ▽ More Data is generated at an unprecedented rate surpassing our ability to analyze them. The database community has pioneered many novel techniques for Approximate Query Processing (AQP) that could give approximate results in a fraction of time needed for computing exact results. In this work, we explore the usage of deep learning (DL) for answering aggregate queries specifically for interactive applications such as data exploration and visualization. We use deep generative models, an unsupervised learning based approach, to learn the data distribution faithfully such that aggregate queries could be answered approximately by generating samples from the learned model. The model is often compact - few hundred KBs - so that arbitrary AQP queries could be answered on the client side without contacting the database server. Our other contributions include identifying model bias and minimizing it through a rejection sampling based approach and an algorithm to build model ensembles for AQP for improved accuracy. Our extensive experiments show that our proposed approach can provide answers with high accuracy and low latency. △ Less

Submitted 18 November, 2019; v1 submitted 24 March, 2019; originally announced March 2019.

Comments: Accepted to ICDE 2020 as "Approximate Query Processing for Data Exploration using Deep Generative Models"

Multi-Attribute Selectivity Estimation Using Deep Learning

Authors: Shohedul Hasan, Saravanan Thirumuruganathan, Jees Augustine, Nick Koudas, Gautam Das

Abstract: Selectivity estimation - the problem of estimating the result size of queries - is a fundamental problem in databases. Accurate estimation of query selectivity involving multiple correlated attributes is especially challenging. Poor cardinality estimates could result in the selection of bad plans by the query optimizer. We investigate the feasibility of using deep learning based approaches for bot… ▽ More Selectivity estimation - the problem of estimating the result size of queries - is a fundamental problem in databases. Accurate estimation of query selectivity involving multiple correlated attributes is especially challenging. Poor cardinality estimates could result in the selection of bad plans by the query optimizer. We investigate the feasibility of using deep learning based approaches for both point and range queries and propose two complementary approaches. Our first approach considers selectivity as an unsupervised deep density estimation problem. We successfully introduce techniques from neural density estimation for this purpose. The key idea is to decompose the joint distribution into a set of tractable conditional probability distributions such that they satisfy the autoregressive property. Our second approach formulates selectivity estimation as a supervised deep learning problem that predicts the selectivity of a given query. We also introduce and address a number of practical challenges arising when adapting deep learning for relational data. These include query/data featurization, incorporating query workload information in a deep learning framework and the dynamic scenario where both data and workload queries could be updated. Our extensive experiments with a special emphasis on queries with a large number of predicates and/or small result sizes demonstrates that our proposed techniques provide fast and accurate selective estimates with minimal space overhead. △ Less

Submitted 17 June, 2019; v1 submitted 24 March, 2019; originally announced March 2019.