In the one-dimensional facility location problem, agents are located on the real line, and a planner's goal is to build one or more facilities on the line to serve the agents. The cost of an agent is her distance to the nearest facility. The problem asks to locate facilities to minimize the total cost of all agents (the utilitarian objective) or the maximum cost among all agents (the egalitarian objective). It is well-known that both optimization problems can be solved in polynomial time [19]. Over the past decade [1, 3, 7, 21, 23, 27], these problems have undergone intensive study from the perspectives of mechanism design and game theory. A key conversion in the models is that now each agent becomes strategic and may misreport her position to decrease her cost. These new problems are called the facility location games, which require to design mechanisms that elicit the true positions of agents and output facility locations to (approximately) minimize the total or maximum cost. Moulin [22] provides a complete characterization of strategyproof mechanisms for the facility location game on line where agents have single-peaked preferences, with no consideration for the optimization of the objective function.

Given a graph, a $k$-plex is a set of vertices 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 the given graph, is an important but computationally challenging problem in applications such as graph mining and community detection. So far, there are many practical algorithms, but without providing theoretical explanations on their efficiency. We define a novel parameter of the input instance, $g_k(G)$, the gap between the degeneracy bound and the size of the maximum $k$-plex in the given graph, and present an exact algorithm parameterized by this $g_k(G)$, which has a worst-case running time polynomial in the size of the input graph and exponential in $g_k(G)$. In real-world inputs, $g_k(G)$ is very small, usually bounded by $O(\log{(|V|)})$, indicating that the algorithm runs in polynomial time. We further extend our discussion to an even smaller parameter $cg_k(G)$, the gap between the community-degeneracy bound and the size of the maximum $k$-plex, and show that without much modification, our algorithm can also be parameterized by $cg_k(G)$. To verify the empirical performance of these algorithms, we carry out extensive experiments to show that these algorithms are competitive with the state-of-the-art algorithms. In particular, for large $k$ values such as $15$ and $20$, our algorithms dominate the existing algorithms. Finally, empirical analysis is performed to illustrate the effectiveness of the parameters and other key components in the implementation.

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 widely adopted as the default partition strategy by existing graph systems. The graph edge partition problem, which is to split the edge set into multiple balanced parts to minimize the total number of copied vertices, has been widely studied from the view of optimization and algorithms. In this paper, we study local search algorithms for this problem to further improve the partition results from existing methods. More specifically, we propose two novel concepts, namely adjustable edges and blocks. Based on these, we develop a greedy heuristic as well as an improved search algorithm utilizing the property of the max-flow model. To evaluate the performance of our algorithms, we first provide adequate theoretical analysis in terms of the approximation quality. We significantly improve the previously known approximation ratio for this problem. Then we conduct extensive experiments on a large number of benchmark datasets and state-of-the-art edge partition strategies. The results show that our proposed local search framework can further improve the quality of graph partition by a wide margin.

The \textsc{Housing Market} problem is a widely studied resource allocation problem. In this problem, each agent can only receive a single object and has preferences over all objects. Starting from an initial endowment, we want to reach a certain assignment via a sequence of rational trades. We first consider whether an object is reachable for a given agent under a social network, where a trade between two agents is allowed if they are neighbors in the network and no participant has a deficit from the trade. Assume that the preferences of the agents are strict (no tie among objects is allowed). This problem is polynomially solvable in a star-network and NP-complete in a tree-network. It is left as a challenging open problem whether the problem is polynomially solvable when the network is a path. We answer this open problem positively by giving a polynomial-time algorithm. Then we show that when the preferences of the agents are weak (ties among objects are allowed), the problem becomes NP-hard even when the network is a path. In addition, we consider the computational complexity of finding different optimal assignments for the problem under the network being a path or a star.

A clique model is one of the most important techniques on the cohesive subgraph detection; however, its applications are rather limited due to restrictive conditions of the model. Hence much research resorts to k -plex — a graph in which any vertex is adjacent to all but at most k vertices — which is a relaxation model of the clique. In this paper, we study the maximum k -plex problem and propose a fast algorithm to compute maximum k -plexes by exploiting structural properties of the problem. In an n -vertex graph, the algorithm computes optimal solutions in c n n O(1) time for a constant c < 2 depending only on k . To the best of our knowledge, this is the first algorithm that breaks the trivial theoretical bound of 2 n for each k ≥ 3. We also provide experimental results over multiple real-world social network instances in support.