Search
Search Results
-
A Sub-quadratic Time Algorithm for Computing the Beacon Kernel of Simple Polygons
In 2011, Biro et al. [4] initiated the concept of beacon attraction trajectory motivated by routing messages in sensor network systems. Let P be a...
-
An Efficient Data Analysis Method for Big Data Using Multiple-Model Linear Regression
This paper introduces a new data analysis method for big data using a newly defined regression model named multiple model linear regression(MMLR),...
-
Linear Time Algorithms for NP-Hard Problems Restricted to GaTEx Graphs
The class of Galled-Tree Explainable (GaTEx) graphs has just recently been discovered as a natural generalization of cographs. Cographs are precisely...
-
Quantum Query Lower Bounds for Key Recovery Attacks on the Even-Mansour Cipher
The Even-Mansour (EM) cipher is one of the famous constructions for a block cipher. Kuwakado and Morii demonstrated that a quantum adversary can...
-
Exponential Time Complexity of the Complex Weighted Boolean #CSP
Cai, Lu, and **a [8] proved a dichotomy for complex weighted Boolean #CSP. If the parameter set of Boolean constraint functions...
-
Diversity and Freshness-Aware Regret Minimizing Set Queries
Multi-criteria decision-making often involves selecting a small representative set from a database. A recently proposed method is the regret...
-
Shortest Longest-Path Graph Orientations
We consider a graph orientation problem that can be viewed as a generalization of Minimum Graph Coloring. Our problem takes as input an undirected...
-
Improved Approximation Algorithms for Multidepot Capacitated Vehicle Routing
The Multidepot Capacitated Vehicle Routing Problem (MCVRP) is a well-known variant of the classic Capacitated Vehicle Routing Problem (CVRP), where...
-
DR-Submodular Function Maximization with Adaptive Stepsize
The DR-submodular function maximization problem has been gaining increasing attention due to its important applications in many fields. In [1], a...
-
Lower Bounds of Functions on Finite Abelian Groups
The problem of computing the optimum of functions on finite abelian groups is an important problem in mathematics and computer science. Many...
-
Topological Network-Control Games
The paper introduces new combinatorial games, called topological network-control games, played on graphs. These games model the influence of...
-
Cabbage Can’t Always Be Transformed into Turnip: Decision Algorithms for Sorting by Symmetric Reversals
Sorting a permutation by reversals is a famous problem in genome rearrangements, and has been well studied over the past thirty years. But the...
-
Fitch Graph Completion
Horizontal gene transfer is an important contributor to evolution. According to Walter M. Fitch, two genes are xenologs if they are separated by at...
-
Solving Systems of Linear Equations Through Zero Forcing Set
Let \(\mathbb {F}\) be any field, we consider...
-
k-Median/Means with Outliers Revisited: A Simple Fpt Approximation
We revisit the classical metric k-median/means with outliers in this paper, whose proposal dates back to (Charikar, Khuller, Mount, and Narasimhan...
-
Hardness and Approximation for the Star \(\beta \) -Hub Routing Cost Problem in \(\varDelta _\beta \) -Metric Graphs
Minimizing transportation costs through the design of a hub-and-spoke network is a crucial concern in hub location problems (HLP). Within the realm...
-
Polynomial Turing Compressions for Some Graph Problems Parameterized by Modular-Width
A polynomial Turing compression (PTC) for a parameterized problem L is a polynomial-time Turing machine that has access to an oracle for a problem...
-
Improved Bounds for the Binary Paint Shop Problem
We improve bounds for the binary paint shop problem posed by Meunier and Neveu [Computing solutions of the paintshop-necklace problem. Comput. Oper....
-
A Modified EXP3 in Adversarial Bandits with Multi-user Delayed Feedback
For the adversarial multi-armed bandit problem with delayed feedback, we consider that the delayed feedback results are from multiple users and are...
-
An Approach to Agent Path Planning Under Temporal Logic Constraints
The capability of path planning is a necessity for an agent to accomplish tasks autonomously. Traditional path planning methods fail to complete...