Search
Search Results
-
A Novel Approximation Algorithm for Max-Covering Circle Problem
We study the efficient approximation algorithm for max-covering circle problem. Given a set of weighted points in the plane and a circle with...
-
GAMA: Genetic Algorithm for k-Coverage and Connectivity with Minimum Sensor Activation in Wireless Sensor Networks
In wireless sensor networks, ensuring k-coverage and connectivity is crucial in order to efficiently gather data and relay it back to the base...
-
On Half Guarding Polygons
Given a polygon P and a set of potential guard locations \(G \in P\)...
-
EFX Allocation to Chores over Small Graph
When allocating indivisible items among agents, achieving envy-free (EF) allocation is not always feasible. Hence a specific area of interest lies in...
-
Multi-Candidate Carpooling Routing Problem and Its Approximation Algorithms
Motivated by the carpooling services, we investigate a new and more challenging scenario for carpooling and model it as the Multi-candidate...
-
Near-Bipartiteness, Connected Near-Bipartiteness, Independent Feedback Vertex Set and Acyclic Vertex Cover on Graphs Having Small Dominating Sets
In the Near-Bipartiteness problem, we are given a simple graph \(G=(V, E)\)...
-
Graph Clustering Through Users’ Properties and Social Influence
Clustering is a basic technology in data mining, and similarity measurement plays a crucial role in it. The existing clustering algorithms,...
-
Information Theory of Blockchain Systems
In this paper, we apply the information theory to provide an approximate expression of the steady-state probability distribution for blockchain...
-
Improved Approximation for Broadcasting in k-Path Graphs
Broadcasting is an information dissemination primitive where a message is passed from one node (called originator) to all other nodes in the network....
-
Critical \((P_5,dart)\) -Free Graphs
Given two graphs \(H_1\) and...
-
The Two Sheriffs Problem: Cryptographic Formalization and Generalization
The two sheriffs problem is the following problem. There are two sheriffs, and each of them has their own list of suspects. Assuming that these lists...
-
Online Facility Assignment for General Layout of Servers on a Line
In the online facility assignment on a line \(\textrm{OFAL}(S,c)\)...
-
Improving Contraction Hierarchies by Combining with All-Pairs Shortest Paths Problem Algorithms
Contraction hierarchies (CH) is a two-phase effective shortest path algorithm for large-scale road networks based on node contraction. However, the...
-
Machine Learning with Low-Resource Data from Psychiatric Clinics
Amidst the rapid growth of big data, the success of machine learning is critically tethered to the availability and quality of training data. A...
-
Some Combinatorial Algorithms on the Dominating Number of Anti-rank k Hypergraphs
Given a hypergraph H(V, E), a set of vertices \(S\subseteq V\)...
-
Earliest Deadline First Is a 2-Approximation for DARP with Time Windows
Dial-a-Ride problems (DARP) require determining a schedule to efficiently serve transportation requests in various scenarios. We consider a variant...
-
Single Image Dehazing Based on Dynamic Convolution and Transformer
In this paper, an end-to-end multi-stage dehazing network based on convolution and Transformer is proposed. The network design is divided into three...
-
Two Exact Algorithms for the Packet Scheduling Problem
We consider a classic packet scheduling problem [7] and its variants. This packet scheduling problem has applications in the areas of logistics, road...
-
Algorithms for the Ridesharing with Profit Constraint Problem
Mobility-on-demand (MoD) ridesharing is a promising way to improve the occupancy rate of personal vehicles and reduce traffic congestion and...
-
Minimum Monotone Tree Decomposition of Density Functions Defined on Graphs
Monotone trees - trees with a function defined on their vertices that decreases the further away from a root node one travels, are a natural model...