Mittagsseminar (in cooperation with J. Lengler, A. Steger, and D. Steurer)

Date and Time: Tuesday, October 18, 2011, 12:15 pm

Duration: 30 minutes

Location: OAT S15/S16/S17

Speaker: Sandro Bosio

A time extension of combinatorial optimization problems

We present an novel model for adding a temporal dimension to classical combinatorial optimization problems. In a static combinatorial optimization problem we are given a set system (A,C) and a linear weight function w, and the goal is to find a member S in C with maximum weight w(S). In the time extended version of the problem, each element a in A is associated with an integral duration t_a. Given a total duration T, a solution over time is a collection of members S_t, for t in {1..T}, with the following property: for each element a in A, the set of time points at which a is selected is a union of intervals whose length is multiple of the duration t_a. That is, each element can be selected any number of times within the time window, but whenever it gets activated it must remain in the solution for its whole duration. The goal is to find a solution over time with maximum total weight (sum of w(S_t) over t in {1..T}).

We present a simple polynomial pq-approximation algorithm for time extensions of independence systems which admit a polynomial q-approximation algorithm for the static version, where p < 1.692. This algorithm generalizes the p-approximation total-value heuristic by Kohli and Krishnamurti (1992) for the integer knapsack problem. We discuss the connection to the integer knapsack and mention some applications to scheduling and orthogonal rectangle packing.

Joint work with David Adjiashvili and Robert Weismantel.

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2025  2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login