3 citations · 11 across the 11 of their papers we have counts for
12 papers
Near-Tight Approximation Algorithms for Bottleneck Multiple Knapsack Problems
Lin Chen, Tingwei Hu, Yuchen Mao +5
In the bottleneck multiple knapsack problem, we are given a set of items and a set of knapsacks, where each item has a profit and a weight, and each knapsack has a capacity. Our go…
Maximizing social welfare among EF1 allocations at the presence of two types of agents
Jiaxuan Ma, Yong Chen, Guangting Chen +3
We study the fair allocation of indivisible items to agents to maximize the utilitarian social welfare, where the fairness criterion is envy-free up to one item and there are o…
Approximation algorithms for non-sequential star packing problems
Mengyuan Hu, An Zhang, Yong Chen +2
For a positive integer , a -star (-star, -star, respectively) is a connected graph containing a degree- vertex and degree- vertices, where $\e…
Approximation algorithms for the directed path partition problems
Yong Chen, Zhi-Zhong Chen, Curtis Kennedy +3
Given a directed graph , the -path partition problem is to find a minimum collection of vertex-disjoint directed paths each of order at most to cover all the ver…
Approximation algorithms for maximally balanced connected graph partition
Yong Chen, Zhi-Zhong Chen, Guohui Lin +2
Given a simple connected graph , we seek to partition the vertex set into non-empty parts such that the subgraph induced by each part is connected, and the part…
A local search -approximation algorithm for the minimum -path partition problem
Yong Chen, Randy Goebel, Guohui Lin +5
Given a graph , the -path partition problem is to find a minimum collection of vertex-disjoint paths each of order at most to cover all the vertices of . It i…
Improved approximation algorithms for path vertex covers in regular graphs
An Zhang, Yong Chen, Zhi-Zhong Chen +1
Given a simple graph and a constant integer , the -path vertex cover problem ({\sc PVC}) asks for a minimum subset of vertices such that…
Approximation algorithms for the three-machine proportionate mixed shop scheduling
Longcheng Liu, Yong Chen, Jianming Dong +6
A mixed shop is a manufacturing infrastructure designed to process a mixture of a set of flow-shop jobs and a set of open-shop jobs. Mixed shops are in general much more complex to…
Approximation algorithms for two-machine flow-shop scheduling with a conflict graph
Yinhui Cai, Guangting Chen, Yong Chen +4
Path cover is a well-known intractable problem that finds a minimum number of vertex disjoint paths in a given graph to cover all the vertices. We show that a variant, where the ob…
On the NP-hardness of scheduling with time restrictions
An Zhang, Yong Chen, Lin Chen +1
In a recent paper, Braun, Chung and Graham [1] have addressed a single-processor scheduling problem with time restrictions. Given a fixed integer , there is a set of jobs…
A local search 2.917-approximation algorithm for duo-preservation string mapping
Yao Xu, Yong Chen, Taibo Luo +1
We study the {\em maximum duo-preservation string mapping} ({\sc Max-Duo}) problem, which is the complement of the well studied {\em minimum common string partition} ({\sc MCSP}) p…
Approximation algorithms for the maximum weight internal spanning tree problem
Zhi-Zhong Chen, Guohui Lin, Lusheng Wang +2
Given a vertex-weighted connected graph , the maximum weight internal spanning tree (MwIST for short) problem asks for a spanning tree of such that the total we…