research
∙
09/05/2023
A 5-approximation Algorithm for the Traveling Tournament Problem
The Traveling Tournament Problem (TTP-k) is a well-known benchmark probl...
share
research
∙
08/31/2023
A Discharging Method: Improved Kernels for Edge Triangle Packing and Covering
Edge Triangle Packing and Edge Triangle Covering are dual problems exten...
research
∙
08/27/2023
Improved Approximation Algorithms for Multidepot Capacitated Vehicle Routing
The Multidepot Capacitated Vehicle Routing Problem (MCVRP) is a well-kno...
research
∙
08/27/2023
The APX-hardness of the Traveling Tournament Problem
The Traveling Tournament Problem (TTP-k) is a well-known benchmark probl...
research
∙
08/27/2023
An Improved Kernel and Parameterized Algorithm for Almost Induced Matching
An induced subgraph is called an induced matching if each vertex is a de...
research
∙
04/18/2023
Connectivity in the presence of an opponent
The paper introduces two player connectivity games played on finite bipa...
research
∙
02/26/2023
MMS Allocations of Chores with Connectivity Constraints: New Methods and New Results
We study the problem of allocating indivisible chores to agents under th...
research
∙
02/18/2023
Characterizations of Network Auctions and Generalizations of VCG
With the growth of networks, promoting products through social networks ...
research
∙
02/17/2023
Multi-unit Auction over a Social Network
Diffusion auction is an emerging business model where a seller aims to i...
research
∙
12/23/2022
Practical Algorithms with Guaranteed Approximation Ratio for TTP with Maximum Tour Length Two
The Traveling Tournament Problem (TTP) is a hard but interesting sports ...
research
∙
12/09/2022
Breaking the Barrier 2^k for Subset Feedback Vertex Set in Chordal Graphs
The Subset Feedback Vertex Set problem (SFVS), to delete k vertices from...
research
∙
10/29/2022
Improved Approximation Algorithms for Capacitated Vehicle Routing with Fixed Capacity
The Capacitated Vehicle Routing Problem (CVRP) is one of the most extens...
research
∙
04/24/2022
Facility Location with Entrance Fees
In mechanism design, the facility location game is an extensively studie...
research
∙
02/17/2022
Listing Maximal k-Plexes in Large Real-World Graphs
Listing dense subgraphs in large graphs plays a key task in varieties of...
research
∙
08/30/2021
A Further Improvement on Approximating TTP-2
The Traveling Tournament Problem (TTP) is a hard but interesting sports ...
research
∙
08/29/2021
Exact algorithms for maximum weighted independent set on sparse graphs
The maximum independent set problem is one of the most important problem...
research
∙
05/13/2021
A Fast Algorithm for SAT in Terms of Formula Length
In this paper, we prove that the general CNF satisfiability problem can ...
research
∙
12/28/2020
Bounded-Degree Cut is Fixed-Parameter Tractable
In the bounded-degree cut problem, we are given a multigraph G=(V,E), tw...
research
∙
12/17/2020
Enhancing Balanced Graph Edge Partition with Effective Local Search
Graph partition is a key component to achieve workload balance and reduc...
research
∙
07/28/2020
The Complexity of the Partition Coloring Problem
Given a simple undirected graph G=(V,E) and a partition of the vertex se...
research
∙
09/17/2019
Object Reachability via Swaps under Strict and Weak Preferences
The Housing Market problem is a widely studied resource allocation probl...
research
∙
09/15/2019
Algorithms for Manipulating Sequential Allocation
Sequential allocation is a simple and widely studied mechanism to alloca...
research
∙
06/26/2019
Upper and Lower Bounds on Approximating Weighted Mixed Domination
A mixed dominating set of a graph G = (V, E) is a mixed set D of vertice...
research
∙
04/09/2018
Characterizing Star-PCGs
A graph G is called a pairwise compatibility graph (PCG, for short) if i...
research
∙
04/09/2018