6 papers
Approximation Algorithms for Perfect Fair-Triangle Packing
Mingyang Gong, Zhi-Zhong Chen, Brendan Mumey
In this paper, we study the {\em perfect fair-triangle packing} problem (abbreviated as PFTP), which incorporates the fairness criterion from {\em fair clustering} into the {\em ma…
Parametric Shortest Paths in a Linearly Interpolated Graph
Jacob Sriraman, Eli Barton, Brittany Terese Fasy +6
We consider the parametric shortest paths problem in a linearly interpolated graph. Given two positively-weighted directed graphs and the linearl…
Offline green bin packing and its constrained variant
Mingyang Gong, Brendan Mumey
In this paper, we study the {\em green bin packing} (GBP) problem where and are two given values as part of the input. The energy consumed by a bin is $\ma…
Approximately Partitioning Vertices into Short Paths
Mingyang Gong, Zhi-Zhong Chen, Brendan Mumey
Given a fixed positive integer and a simple undirected graph , the {\em -path partition} problem, denoted by PP for short, aims to find a minimum collection…
Approximation algorithms for scheduling with rejection in green manufacturing
Mingyang Gong, Brendan Mumey
Motivated by green manufacturing, this paper investigates a scheduling with rejection problem subject to an energy consumption constraint. Machines are associated with non-uniform…
An improved local search based algorithm for -star partition
Mingyang Gong, Guohui Lin, Brendan Mumey
We study the -star partition problem that aims to find a minimum collection of vertex-disjoint stars, each having at most vertices to cover all vertices in a simple undire…