Search

We consider a general class of binary packing problems with a convex quadratic knapsack constraint. We prove that these problems are APX-hard to approximate and present constant-factor approximation algorithms based upon three different algorithmic techniques: (1) a rounding technique tailored to a convex relaxation in conjunction with a non-convex relaxation whose approximation ratio equals the golden ratio; (2) a greedy strategy; (3) a randomized rounding method leading to an approximation algorithm for the more general case with multiple convex quadratic constraints. We further show that a combination of the first two strategies can be used to yield a monotone algorithm leading to a strategyproof mechanism for a game-theoretic variant of the problem. Finally, we present a computational study of the empirical approximation of the three algorithms for problem instances arising in the context of real-world gas transport networks.

In a digraph with a source and several destination nodes with associated demands, an unsplittable flow routes each demand along a single path from the common source to its destination. Given some flow x that is not necessarily unsplittable but satisfies all demands, it is a natural question to ask for an unsplittable flow y that does not deviate from x by too much, i.e., \(y_a\approx x_a\) for all arcs a. Twenty years ago, in a landmark paper, Dinitz, Garg, and Goemans [3] proved that there is an unsplittable flow y such that \(y_a\le x_a+d_{\max }\) for all arcs a, where \(d_{\max }\) denotes the maximum demand value.

Robotic welding cells are at the core of many complex production systems, especially in automotive industry. In these cells, a certain number of robots perform spot welding tasks on a workpiece. The configuration of the cells can have a huge impact on the production rate. The smaller the cycle time is, the higher the production is. In this paper, we present a complete algorithm that automatically configures the welding cell such that the given cycle time of the production process is kept. This algorithm assigns tasks to the different robots, decides in which order the tasks are executed and computes the fastest collision-free trajectory of the robots between two consecutive tasks.

Sustainable manufacturing is driven by the insight that the focus on the economic dimension in current businesses and lifestyles has to be broadened to cover all three pillars of sustainability: economic development, social development, and environmental protection.

We consider the optimization problem of scheduling a given set of jobs on unrelated parallel machines with total weighted completion time objective. This is a classical scheduling problem known to be NP-hard since the 1970s. We give a new and simplified version of the currently best-known approximation algorithm, which dates back to 1998. It achieves performance ratio 3 / 2, and is based on an optimal solution to a convex quadratic program.

Are you looking for new lectures for your course on algorithms, combinatorial optimization, or algorithmic game theory? Maybe you need a convenient source of relevant, current topics for a graduate student or advanced undergraduate student seminar? Or perhaps you just want an enjoyable look at some beautiful mathematical and algorithmic results, ideas, proofs, concepts, and techniques in discrete mathematics and theoretical computer science?Gems of Combinatorial Optimization and Graph Algorithms is a handpicked collection of up-to-date articles, carefully prepared by a select group of international experts, who have contributed some of their most mathematically or algorithmically elegant ideas. Topics include longest tours and Steiner trees in geometric spaces, cartograms, resource buying games, congestion games, selfish routing, revenue equivalence and shortest paths, scheduling, linear structures in graphs, contraction hierarchies, budgeted matching problems, and motifs in networks.This volume is aimed at readers with some familiarity of combinatorial optimization, and appeals to researchers, graduate students, and advanced undergraduate students alike.

Flows over time are used to model many real-world logistic and routing problems. The networks underlying such problems – streets, tracks, etc. – are inherently undirected and directions are only imposed on them to reduce the danger of colliding vehicles and similar problems. Thus the question arises, what influence the orientation of the network has on the network flow over time problem that is being solved on the oriented network. In the literature, this is also referred to as the contraflow or lane reversal problem.