@misc{HarksHeinzPfetsch, author = {Harks, Tobias and Heinz, Stefan and Pfetsch, Marc}, title = {Competitive Online Multicommodity Routing}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9599}, number = {07-16}, abstract = {In this paper we study online multicommodity routing problems in networks, in which commodities have to be routed sequentially. The flow of each commodity can be split on several paths. Arcs are equipped with load dependent price functions defining routing costs, which have to be minimized. We discuss a greedy online algorithm that routes each commodity by minimizing a convex cost function that only depends on the demands previously routed. We present a competitive analysis of this algorithm showing that for affine linear price functions this algorithm is 4K2 (1+K)2 -competitive, where K is the number of commodities. For the single-source single-destination case, this algorithm is optimal. Without restrictions on the price functions and network, no algorithm is competitive. Finally, we investigate a variant in which the demands have to be routed unsplittably.}, language = {en} } @misc{JokarPfetsch, author = {Jokar, Sadegh and Pfetsch, Marc}, title = {Exact and Approximate Sparse Solutions of Underdetermined Linear Equations}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9488}, number = {07-05}, abstract = {In this paper, we empirically investigate the NP-hard problem of finding sparse solutions to linear equation systems, i.e., solutions with as few nonzeros as possible. This problem has received considerable interest in the sparse approximation and signal processing literature, recently. We use a branch-and-cut approach via the maximum feasible subsystem problem to compute optimal solutions for small instances and investigate the uniqueness of the optimal solutions. We furthermore discuss five (modifications of) heuristics for this problem that appear in different parts of the literature. For small instances, the exact optimal solutions allow us to evaluate the quality of the heuristics, while for larger instances we compare their relative performance. One outcome is that the basis pursuit heuristic performs worse, compared to the other methods. Among the best heuristics are a method due to Mangasarian and a bilinear approach.}, language = {en} }