Search
Search Results
-
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...
-
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...
-
Mechanism Design for Time-Varying Value Tasks in High-Load Edge Computing Markets
A large number of computing task requests are generated by user terminals during peak hours in high-demand areas, but the resource capacity of edge...
-
Maximizing Utilitarian and Egalitarian Welfare of Fractional Hedonic Games on Tree-Like Graphs
Fractional hedonic games are coalition formation games where the utility of a player is determined by the average value they assign to the members of...
-
Testing Higher-Order Clusterability on Graphs
Analysis of higher-order organizations, usually small connected subgraphs called motifs, is a fundamental task on complex networks. This paper...
-
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...
-
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...
-
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...
-
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...
-
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\)...
-
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...
-
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...
-
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,...
-
Online Facility Assignment for General Layout of Servers on a Line
In the online facility assignment on a line \(\textrm{OFAL}(S,c)\)...
-
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...
-
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...
-
Dynamic Programming for the Fixed Route Hybrid Electric Aircraft Charging Problem
Air mobility is rapidly moving towards the development and usage of hybrid electric aircraft in multi-flight missions. Aircraft operators must...
-
An Efficient Local Search Algorithm for Correlation Clustering on Large Graphs
Correlation clustering (CC) is a widely-used clustering paradigm, with many applications to problems such as classification, database deduplication,...
-
On Half Guarding Polygons
Given a polygon P and a set of potential guard locations \(G \in P\)...
-
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)\)...