29 accepted papers
The Kidney Exchange Problem is a prominent challenge in healthcare and economics, arising in the context of organ transplantation. It has been extensively studied in artificial intelligence and optimization. In a kidney exchange, a set of donor-recipient pairs and altruistic donors are considered, w
In some professional sports leagues, inter-league games are scheduled among multiple divisions or conferences. This inspired us to study the p-partite Traveling Tournament Problem (p-partite TTP), where teams are partitioned into p leagues, and each team plays games against teams from different leag
TSP is a classic and extensively studied problem with numerous real-world applications in artificial intelligence and operations research. It is well-known that TSP admits a constant approximation ratio on metric graphs but becomes NP-hard to approximate within any computable function f(n) on genera
In knockout tournaments, players compete in successive rounds, with losers eliminated and winners advancing until a single champion remains. Given a tournament digraph D, which encodes the outcomes of all possible matches, and a designated player v* in V(D), the Tournament Fixing problem (TFP) asks
The Ride-Sharing Assignment Problem (AAAI 2018) is a fundamental problem in intelligent transportation systems, urban mobility, and algorithmic decision-making. Given a set of m vehicles with initial locations and n requests (n≤mk), each with a specified origin and destination, the goal is to assign
The Tournament Fixing Problem (TFP) asks whether a knockout tournament can be scheduled to guarantee that a given player v* wins. Although TFP is NP-hard in general, it is known to be fixed-parameter tractable (FPT) when parameterized by the feedback arc/vertex set number, or the in/out-degree of v*
Human Activity Recognition (HAR) is crucial for applications like urban traffic management and health monitoring but faces challenges in handling complex patterns and missing sensor data. In this work, we propose a conditional Kolmogorov-Arnold network diffusion (CKAD) framework for HAR, which separ…
The Traveling Tournament Problem (TTP-k) is a well-known benchmark problem in tournament timetabling. It involves designing a feasible double round-robin tournament for a sports league of n teams under several feasibility requirements, while minimizing the total traveling costs of the teams. The par…
We introduce Crowd-Sourced Splatting (CSS), a novel 3D Gaussian Splatting (3DGS) pipeline designed to overcome the challenges of pose-free scene reconstruction using crowd-sourced imagery. The dream of reconstructing historically significant but inaccessible scenes from collections of photographs ha…
In the Clustered TSP (CTSP), we are given an edge-weighted graph satisfying the triangle inequality property, and a family of pairwise disjoint vertex groups. The goal is to find a minimum weight tour that includes all vertices, ensuring that the vertices within each group appear consecutively on t…
Map-free visual relocalization computes camera pose using only a query image and a reference image. Therefore, it is hindered by challenges in feature-point matching and the absence of scale information in monocular images. These issues may cause significant rotational and metric errors, leading to…
The #2-SAT and #3-SAT problems involve counting the number of satisfying assignments (also called models) for instances of 2-SAT and 3-SAT, respectively. In 2010, Zhou et al. (https://doi.org/10.1609/aaai.v24i1.7537) proposed an O*(1.1892^m)-time algorithm for #2-SAT and an efficient approach for #3
Recently, significant advancements have been made in 3D Gaussian Splatting SLAM for dynamic environments. However, most existing methods primarily address active dynamic objects, such as people and vehicles, and fail to account for the impact of passive dynamic objects on localization and mapping. T
Strategyproofness in network auctions requires that bidders not only report their valuations truthfully, but also do their best to invite neighbours from the social network. In contrast to canonical auctions, where the value-monotone allocation in Myerson's Lemma is a cornerstone, a general principl
The bipartite traveling tournament problem (BTTP) was initially introduced by Hoshino and Kawarabayashi (AAAI 2011) to address inter-league sports scheduling, which aims to design a feasible bipartite tournament between two n-team leagues under some constraints such that the total traveling distance…
We study the following parameterization of the MaxSAT problem: Given a CNF formula F with m clauses, decide whether at least m/2 + μ clauses in F could be satisfied, where μ is the excess of the number of satisfied clauses over the trivial lower bound m/2 and is taken as the parameter. This perspec…
The maximum vertex-weighted clique problem (MVWCP) and the maximum edge-weighted clique problem (MEWCP) are two natural extensions of the fundamental maximum clique problem. In this paper, we systematically study MEWCP and make the following major contributions: (1) We show that MEWCP is NP-hard ev…
The Minimum Dominating Set Problem (MDSP) is an important NP-Hard optimization problem with many applications in various domains. This paper designs two exact algorithms for MDSP that use the same Branch-and-Bound framework. However, one uses LP relaxations as lower bounds for pruning the search spa…
The Capacitated Location Routing Problem is an important planning and routing problem in logistics, which generalizes the capacitated vehicle routing problem and the uncapacitated facility location problem. In this problem, we are given a set of depots and a set of customers where each depot has an…
Given a graph, the k-plex is a vertex set in which each vertex is not adjacent to at most k-1 other vertices in the set. The maximum k-plex problem, which asks for the largest k-plex from a given graph, is an important but computationally challenging problem in applications like graph search and com…
The facility location game is an extensively studied problem in mechanism design. In the classical model, the cost of each agent is her distance to the nearest facility. In this paper, we consider a novel model where each facility charges an entrance fee, which is a function of the facility's locati…
We present fast algorithms for the general CNF satisfiability problem (SAT) with running-time bound O*({c_d}^n), where c_d is a function of the maximum occurrence d of variables (d can also be the average occurrence when each variable appears at least twice), and n is the number of variables in the…
The Traveling Tournament Problem (TTP-k) is a well-known benchmark problem in tournament timetabling and has been extensively studied in the field of AI. In this problem, we are going to design a double round-robin schedule such that each pair of teams plays one game in each other's home venue, mini…
In the maximum satisfiability problem (MaxSAT), given a CNF formula with m clauses and n variables, we are asked to find an assignment of the variables to satisfy the maximum number of clauses. Chen and Kanj showed that this problem can be solved in O*(1.3248^m) time (DAM 2004) and the running time…
We study multi-unit auctions in social networks, where each buyer has a fixed budget and can spread the sale information to the network neighbors. We design a mechanism encouraging buyers to report their valuations truthfully and spread the sale information. Our design uses the idea of the clinching…
We show that the CNF satisfiability problem can be solved O^*(1.2226^m) time, where m is the number of clauses in the formula, improving the known upper bounds O^*(1.234^m) given by Yamamoto 15 years ago and O^*(1.239^m) given by Hirsch 22 years ago. By using an amortized technique and careful case…
Graph partition is a key component to achieve workload balance and reduce job completion time in parallel graph processing systems. Among the various partition strategies, edge partition has demonstrated more promising performance in power-law graphs than vertex partition and thereby has been more w…
In a graph, a k-plex is a vertex set in which every vertex is not adjacent to at most k vertices of this set. The maximum k-plex problem, which asks for the largest k-plex from the given graph, is a key primitive in a variety of real-world applications like community detection and so on. In the pape…
The Traveling Tournament Problem is a well-known benchmark problem in tournament timetabling, which asks us to design a schedule of home/away games of n teams (n is even) under some feasibility requirements such that the total traveling distance of all the n teams is minimized. In this paper, we stu…