BEGIN:VCALENDAR
VERSION:2.0
PRODID:Linklings LLC
BEGIN:VTIMEZONE
TZID:America/Chicago
X-LIC-LOCATION:America/Chicago
BEGIN:DAYLIGHT
TZOFFSETFROM:-0600
TZOFFSETTO:-0500
TZNAME:CDT
DTSTART:19700308T020000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=2SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0500
TZOFFSETTO:-0600
TZNAME:CST
DTSTART:19701101T020000
RRULE:FREQ=YEARLY;BYMONTH=11;BYDAY=1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTAMP:20210808T235336Z
LOCATION:Room C
DTSTART;TZID=America/Chicago:20210811T103000
DTEND;TZID=America/Chicago:20210811T104500
UID:icpp_ICPP 2021_sess125_pap444@linklings.com
SUMMARY:Generalized Skyline Interval Coloring and Dynamic Geometric Bin Pa
cking Problems
DESCRIPTION:Conference Paper\n\nGeneralized Skyline Interval Coloring and
Dynamic Geometric Bin Packing Problems\n\nRen, Tang\n\nWe consider two com
binatorial optimization problems, named Generalized Skyline Interval Color
ing (GSIC) and Dynamic Geometric Bin Packing (DGBP). The input to both pro
blems is a set of interval jobs, with each job specified by a horizontal a
ctive time interval and a vertical size. For GSIC, each job is to be alloc
ated a vertical interval of the specified size in the range $[0, +\infty)$
. For any two jobs with overlapping active intervals, their vertical inter
vals must not overlap. The instantaneous cost of an allocation at any time
is defined as the highest point allocated to the active jobs. The target
is to minimize the accumulated cost over time. For DGBP, each job is to be
assigned to a machine of capacity $g$ and be allocated a vertical interva
l of the specified size in the range $[0, g)$. For any two jobs with overl
apping active intervals, if they are assigned to the same machine, their v
ertical intervals must not overlap. The target is to minimize the total ma
chine busy time, where the busy time of a machine is the time duration in
which there is at least one active job in the machine. We develop $O(1)$-a
pproximation algorithms for both problems in the offline setting and asymp
totically optimal algorithms in the non-clairvoyant and clairvoyant online
settings.
END:VEVENT
END:VCALENDAR