A Combinatorial 2-Approximation Algorithm for the Parallel-Machine Scheduling with Release Times and Submodular Penalties

Article Computer Science, Interdisciplinary Applications

Combinatorial approximation algorithms for the submodular multicut problem in trees with submodular penalties

Xiaofei Liu et al.

Summary: In this paper, the submodular multicut problem in trees with submodular penalties is introduced, and two combinatorial approximation algorithms are presented for solving this problem and a special case with modular edge cost.

JOURNAL OF COMBINATORIAL OPTIMIZATION (2022)

Add to Collection

Article Operations Research & Management Science

A primal-dual approximation algorithm for the k-prize-collecting minimum power cover problem

Xiaofei Liu et al.

Summary: This paper introduces the k-prize-collecting minimum power cover problem and presents a novel two-phase primal-dual algorithm with an approximation ratio of at most 3(alpha).

OPTIMIZATION LETTERS (2022)

Add to Collection

Article Operations Research & Management Science

Online algorithms for the mixed ring loading problem with two nodes

Li Guan et al.

Summary: This paper introduces the mixed ring loading problem with undirected and bidirected links. The study focuses on a two-node ring and addresses the online mixed ring loading problem under scenarios of splittable, integer splittable, and unsplittable demands. It presents (asymptotically) optimal online algorithms for splittable demands and a generalized online algorithm for unsplittable demands based on previous results.

OPTIMIZATION LETTERS (2021)

Add to Collection

Article Operations Research & Management Science

Approximation algorithms for the multiprocessor scheduling with submodular penalties

Xiaofei Liu et al.

Summary: This paper discusses multiprocessor scheduling with submodular penalties, aiming to minimize the sum of makespan and rejection penalty by finding a subset of rejected jobs and assigning others to machines. Non-combinatorial and combinatorial algorithms are proposed for worst-case guarantee and special case scenarios, respectively.

OPTIMIZATION LETTERS (2021)

Add to Collection

Article Mathematics

Single Machine Vector Scheduling with General Penalties

Xiaofei Liu et al.

Summary: This paper studies the single machine vector scheduling problem with general penalties and presents approximation algorithms and lower bound proofs.

MATHEMATICS (2021)

Add to Collection

Article Mathematics, Applied