doi:10.1016/j.orl.2004.07.001 (2009)
R. K. Ahuja, T. L. Magnanti, J. B. Orlin, Hans Kellerer, Ulrich Pferschy, David Pisinger, ...
I cannot help but start this review with an analogy between the knapsack problem and the traveling salesman problem (TSP), the two most studied problems of combinatorial optimization. Both problems...
Nordic Journal of Computing 1(1994), 246–263. SOME GEOMETRIC CLUSTERING PROBLEMS ∗ (2008)
Ulrich Pferschy, Rüdiger Rudolf, Tu Graz, Gerhard J. Woeginger
Abstract. This paper investigates the computational complexity of several clustering problems with special objective functions for point sets in the Euclidean plane. Our strongest negative result is...
Solving the Prize-Collecting Steiner Tree Problem to Optimality ⋆ (2008)
Ivana Ljubi, René Weiskircher, Ulrich Pferschy, Gunnar Klau, Petra Mutzel, Ivana Ljubić, ...
www.cg.tuwien.ac.at
Ulrich Pferschy, Gerhard J. Woeginger
Text--compression problems are considered where substrings are substituted by code--words according to a static dictionary such that the original text is encoded by a shorter code sequence. We...
Approximation schemes for ordered vector packing problems (2007)
Alberto Caprara, Hans Kellerer, Ulrich Pferschy
In this paper we deal with the d-dimensional vector packing problem, which is a generalization of the classical bin packing problem in which each item has d distinct weights and each bin has d...
The multidimensional knapsack problem: Structure and algorithms (2007)
Jakob Puchinger, Günther R. Raidl, Ulrich Pferschy
We study the multidimensional knapsack problem, present some theoretical and empirical results about its structure, and evaluate different Integer Linear Programming (ILP) based, metaheuristic, and...
The Core Concept for the Multidimensional (2006)
Knapsack Problem Jakob, Jakob Puchinger, Günther R. Raidl, Ulrich Pferschy
We present the newly developed core concept for the Multidimensional Knapsack Problem (MKP) which is an extension of the classical concept for the one-dimensional case. The core for the...
Solving the prize-collecting Steiner tree problem to optimality (2005)
Ivana Ljubić, René Weiskircher, Ulrich Pferschy, Gunnar Klau, Petra Mutzel
The Prize-Collecting Steiner Tree Problem (PCST) on a graph with edge costs and vertex profits asks for a subtree minimizing the sum of the total cost of all edges in the subtree plus the total...
Gunnar W. Klau, Ivana Ljubic, Andreas Moser, Petra Mutzel, Philipp Neuner, Ulrich Pferschy, ...
The prize-collecting Steiner tree problem on a graph with edge costs and vertex profits asks for a subtree minimizing the sum of the total cost of all edges in the subtree plus the total profit of...
Solving the Prize-Collecting Steiner Tree Problem (2004)
Ivana Lubic, Ivana Ljubić, René Weiskircher, René Weiskircher, Ulrich Pferschy, Ulrich Pferschy, ...
The Prize-Collecting Steiner Tree Problem (PCST) on a graph with edge costs and vertex profits asks for a subtree minimizing the sum of the total cost of all edges in the subtree plus the total...
Gunnar W. Klau, Ivana Ljubic, Andreas Moser, Petra Mutzel, Philipp Neuner, Ulrich Pferschy, ...
The prize-collecting Steiner tree problem on a graph with edge costs and vertex profits asks for a subtree minimizing the sum of the total cost of all edges in the subtree plus the total profit of...
The fractional prize-collecting Steiner tree problem on trees (2003)
Gunnar W. Klau, Gunnar W. Klau, Ivana Ljubić, Ivana Ljubić, Petra Mutzel, Petra Mutzel, ...
Abstract. We consider the fractional prize-collecting Steiner tree problem on trees. This problem asks for a subtree T containing the root of a given tree G = (V, E) maximizing the ratio of the...
A 3/4-approximation algorithm for multiple subset sum (2003)
Alberto Caprara, Hans Kellerer, Ulrich Pferschy
The Multiple Subset Sum Problem (MSSP) is the variant of bin packing in which the number of bins is given and one would like to maximize the overall weight of the items packed in the bins. The...
The Fractional Prize-Collecting Steiner Tree Problem on Trees (Extended Abstract) (2003)
Gunnar W. Klau, Ivana Ljubic, Petra Mutzel, Ulrich Pferschy, Rene Weiskircher
Gunnar W. Klau , Ivana Ljubic , Petra Mutzel Ulrich Pferschy , and Rene Weiskircher Institute of Computer Graphics and Algorithms, Vienna University of Technology, Austria...
Approximation algorithms for knapsack problems with cardinality constraints (2000)
Alberto Caprara, Hans Kellerer, Ulrich Pferschy, David Pisinger
We address a variant of the classical knapsack problem in which an upper bound is imposed on the number of items that can be selected. This problem arises in the solution of real-life cutting stock...
The Multiple Subset Sum Problem (2000)
Alberto Caprara, Hans Kellerer, Ulrich Pferschy
The Multiple Subset Sum Problem (MSSP) is the selection of items from a given ground set and their packing into a given number of identical bins such that the sum of the item weights in every bin...
Approximation algorithms for knapsack problems with cardinality constraints (2000)
Alberto Caprara, Hans Kellerer, Ulrich Pferschy, David Pisinger
y--We address a variant of the classical knapsack problem in which an upper bound is imposed on the number of items that can be selected. This problem arises in the solution of real-life cutting...
A New Fully Polynomial Approximation Scheme for the Knapsack Problem (1998)
Hans Kellerer, Ulrich Pferschy
A new fully polynomial approximation scheme (FPTAS) is presented for the classical 0--1 knapsack problem. It considerably improves the space requirements. The two best previously known approaches...
Approximation Algorithms for Knapsack Problems with Cardinality Constraints (1997)
Alberto Caprara, Hans Kellerer, Ulrich Pferschy, David Pisinger
We address a variant of the classical knapsack problem in which an upper bound is imposed on the number of items that can be selected. This problem arises in the solution of real-life cutting stock...
Stochastic Analysis of Greedy Algorithms for the Subset Sum Problem (1997)
The subset sum problem is the selection of a subset of items from a given ground set summing up as close as possible to a given capacity value. In this paper we deal with the probabilistic analysis...
On-line Waste Management in a. . . (1996)
Diskrete Optimierung, Rainer E. Burkard, Rainer E. Burkard, Ulrich Pferschy, Ulrich Pferschy, ...
In this paper we present a case study of a waste--water treatment procedure for a zinc galvanization unit of a metal--processing company. During the process of galvanization several types of...
Worst-Case Analysis for On-Line Data Compression (1995)
József Békési, Gábor Galambos, Ulrich Pferschy, Gerhard J. Woeginger
Introduction and Definitions: Modern computations apply many variants of data compression. We treat the compression of a given source--string by substituting pieces of the string with the help of a...
Monge Matrices Make Maximization Manageable (1993)
Diskrete Optimierung, Rüdiger Rudolf, Ulrich Pferschy, Ulrich Pferschy, Rudiger Rudolf, Gerhard J. Woeginger, ...
. We continue the research on the effects of Monge structures in the area of combinatorial optimization. We show that three optimization problems become easy if the underlying cost matrix fulfills...
Some Geometric Clustering Problems (1993)
Diskrete Optimierung, Rüdiger Rudolf, Ulrich Pferschy, Ulrich Pferschy, Rudiger Rudolf, Gerhard J. Woeginger, ...
This paper investigates the computational complexity of several clustering problems with special objective functions for point sets in the Euclidean plane. Our strongest negative result is that...
Approximation algorithms for knapsack problems with cardinality constraints
Caprara, Alberto, Kellerer, Hans, Pferschy, Ulrich, Pisinger, David
Maximizing the minimum voter satisfaction on spanning trees
Darmann, Andreas, Klamler, Christian, Pferschy, Ulrich
This paper analyzes the computational complexity involved in solving fairness issues on graphs, e.g., in the installation of networks such as water networks or oil pipelines. Based on individual...