Open for all UnRAVeL Members: 3rd Gerhard Woeginger Research Colloquium of the Center of Algorithmics and Optimization

Friday, November 24, 2023, 2:30pm

Location: SeMath, Pontdriesch 14-16

Schedule:

2:30 -- 2:40 pm: Welcome and news from the center
2:40 -- 3:45 pm: Lars Rohwedder (University of Maastricht): Simpler and stronger approximation algorithms for flow time scheduling
3:45 -- 4:15 pm: Coffee Break in Math Lounge (3rd floor)
4:15 --5:15 pm: Contributed talks by  Daniel Mock, Lorena Reyes Rubiano, and Jenny Segschneider (all RWTH Aachen)

 

Abstracts:

 

Lars Rohwedder (University of Maastricht): Simpler and stronger approximation algorithms for flow time scheduling

Flow time measures the duration from release until completion of a job. It is one of the most natural, but also most notorious objectives in scheduling. In their influential survey from 1999, Schuurman and Woeginger already highlighted the open question of obtaining a polynomial time constant approximation for minimizing the sum of weighted flow times in the seemingly simple single machine setting. This was only recently solved in a combination of a tour-de-force by Batra, Garg, and Kumar and a clever instance reduction by Feige, Kulkarni, and Li. Afterwards, Armbruster, Wiese, and I improved this to a PTAS. Out of these insights we were also able to derive a much simpler constant approximation algorithm, for which I will give close to a full proof here. At the end of the talk, I will conclude with some related open questions.

 

Daniel Mock (Chair of Theoretical Computer Science, RWTH): Solving a Family of Multivariate Optimization and Decision Problems on Classes of Bounded Expansion

Many NP-hard or W[1]-hard problems are (fixed-parameter) tractable when restricted to special graph classes, especially sparse ones like planar graphs, graphs of bounded treewidth or even graph classes excluding minors. This is prominently captured by powerful meta-theorems like Courcelle's theorem or the result of Grohe, Kreutzer and Siebertz: Every problem expressible in first-order logic is fixed-parameter tractable on nowhere dense classes of graphs. Classes of bounded expansion and those classes generalize many familiar classes of sparse graphs and are in some sense the most general robust notion of sparsity. For example, this result implies that the k-Dominating Set Problem has an f(k) n^(1+o(1)) algorithm on all nowhere dense classes. However, it does not cover problems that use counting in some sense as first-order logic is not able to count. An example is the Partial Dominating Set Problem which asks, given integers k and t, for a set of k vertices that dominate t vertices. Or the Partial Red-Blue Dominating Set problem which asks to find k vertices that dominate t_r of the red and t_b of the blue vertices. Those problems can be expressed in the counting logic FO(>0) which augments first-order logic with a special kind of counting quantifiers.  

Our contribution is a model-checking algorithm for formulas of the form ''ψ ≡ ∃x₁...∃xₖ P(#y ϕ_1(x₁...xₖ,y), ..., #y ϕ_r(x₁...xₖ,y))'', where P is some predicate on numbers and ϕ_i are first-order formulas. The running time is f(|ψ|)n^(r+1) polylog(n) on graph classes of bounded expansion. We also provide a lower bound under SETH which is tight up to an almost linear factor.

In this talk, I will present the notion of sparsity in graphs, especially classes of bounded expansion, some known meta-theorems for logics with and without counting, and our contribution (without any proofs!).

 

Jenny Segschneider (LuF Discrete Optimization, RWTH): Including Uncertain Capacity in  b-matchings while remaining robust

The b-matching problem is a well-known variant of the famous matching problem with many applications. Given an undirected graph, each vertex v has to be matched b(v) times and edges can be used multiple times. It is also solvable in polynomial time. Applications include matching workers or produce to customers, as in the Chinese Postman Problem, but it is also used in Heuristics for other well-known Problems like TSP. In theory, the capacity b(v) is fixed and known for each vertex. However, in practice, the capacity is often subject to uncertainties, as workers get sick or customers drop out.

In this talk, we present a new variant of the b-matching problem under uncertain capacity ensuring robustness, called the robust directed b-matching problem. An instance of the problem consists of a directed graph with costs on each arc and uncertain capacities on each vertex. The problem has two stages: first, we set the sum of the matching over all outgoing arcs for each vertex. Second, after realization of the uncertain capacity, we set the b-matching minimizing the costs.

We examine the problem's complexity on different graph classes and show NP-hardness even on directed trees, which are directed acycle graphs whose underlying undirected graph is a tree. We also showcase the influence of requiring a perfect matching, where each vertex has to be matched exactly b(v) times, which turns out to make the problem easier on some graph classes.

This is joint work with Arie Koster.

 

Lorena Reyes Rubiano (Chair of Business Analytics, RWTH): Revenue Maximizing Tariff Zone Planning for Public Transport Service Companies

We propose a new mathematical approach for designing a counting zone tariff system in public transportation. The goal is to maximize revenue while considering spatial patterns like rings or stripes in the resulting zones. The approach assumes discrete zone prices, trip numbers influenced by prices, and passengers choosing the time-shortest path. We present a Lagrangian approximation method, scaling linearly with the number of stops. Extensive numerical studies evaluate network and demand structures. The approach achieves optimal solutions for instances with 121 stops within a few hours. Instances with over 500 stops can be solved in under an hour. Findings show that revenue increases with network connectivity, spatial patterns may slightly decrease revenue (stripes less than rings), and time-shortest paths mostly always come at minimum cost. A case study of the San Francisco Bay Area with 1,400 stops demonstrates the approach's practicality. Enforcing a stripe pattern results in more balanced zone areas but sacrifices 3-5% of optimal revenue compared to no pattern.