120 citations · 268 across the 16 of their papers we have counts for
21 papers
Inclusion-wise extremal knapsack problems are (mostly) hard to approximate
Fabio Ciccarelli, Fabio Furini, Ulrich Pferschy +1
We study two inclusion-wise extremal variants of the 0-1 Knapsack Problem (KP). Given items with integer weights and nonnegative costs or profits, the Minimum-Cost Maximal Knap…
Scheduling with Time Dependent Utilities: Fairness and Efficiency
Gaia Nicosia, Andrea Pacifici, Ulrich Pferschy
A new class of multi agent single machine scheduling problems is introduced, where each job is associated with a self interested agent with a utility function decreasing in complet…
Flow Shop Scheduling with Inter-Stage Flexibility and Blocking Constraints
Gaia Nicosia, Andrea Pacifici, Ulrich Pferschy +2
We investigate a scheduling problem arising from a material handling and processing problem in a production line of an Austrian company building prefabricated house walls. The addr…
Allocation of Indivisible Items with a Common Preference Graph: Minimizing Total Dissatisfaction
Nina Chiarelli, Clément Dallard, Andreas Darmann +4
Allocating indivisible items among a set of agents is a frequently studied discrete optimization problem. In the setting considered in this work, the agents' preferences over the i…
Minimizing Maximum Dissatisfaction in the Allocation of Indivisible Items under a Common Preference Graph
Nina Chiarelli, Clément Dallard, Andreas Darmann +4
We consider the task of allocating indivisible items to agents, when the agents' preferences over the items are identical. The preferences are captured by means of a directed acycl…
REDS: Resource-Efficient Deep Subnetworks for Dynamic Resource Constraints
Francesco Corti, Balz Maag, Joachim Schauer +2
Deep learning models deployed on edge devices frequently encounter resource variability, which arises from fluctuating energy levels, timing constraints, or prioritization of other…
Fair Allocation Algorithms for Indivisible Items under Structured Conflict Constraints
Nina Chiarelli, Matjaž Krnc, Martin Milanič +2
We consider the fair allocation of indivisible items to several agents with additional conflict constraints. These are represented by a conflict graph where each item corresponds t…
Operational Research: Methods and Applications
Fotios Petropoulos, Gilbert Laporte, Emel Aktas +79
Throughout its history, Operational Research has evolved to include a variety of methods, models and algorithms that have been applied to a diverse and wide range of contexts. This…
Integrating multiple sources of ordinal information in portfolio optimization
Eranda Çela, Stephan Hafner, Roland Mestel +1
Active portfolio management tries to incorporate any source of meaningful information into the asset selection process. In this contribution we consider qualitative views specified…
Allocation of Indivisible Items with Individual Preference Graphs
Nina Chiarelli, Clément Dallard, Andreas Darmann +5
This paper studies the allocation of indivisible items to agents, when each agent's preferences are expressed by means of a directed acyclic graph. The vertices of each preference…
Optimally rescheduling jobs with a LIFO buffer
Gaia Nicosia, Andrea Pacifici, Ulrich Pferschy +2
This paper considers single-machine scheduling problems in which a given solution, i.e. an ordered set of jobs, has to be improved as much as possible by re-sequencing the jobs. Th…
Fair allocation of indivisible items with conflict graphs
Nina Chiarelli, Matjaž Krnc, Martin Milanič +3
We consider the fair allocation of indivisible items to several agents and add a graph theoretical perspective to this classical problem. Namely, we introduce an incompatibility re…
The Product Knapsack Problem: Approximation and Complexity
Ulrich Pferschy, Joachim Schauer, Clemens Thielen
We consider the product knapsack problem, which is the variant of the classical 0-1 knapsack problem where the objective consists of maximizing the product of the profits of the se…
Geometric and LP-based heuristics for the quadratic travelling salesman problem
Rostislav Staněk, Peter Greistorfer, Klaus Ladner +1
A generalization of the classical TSP is the so-called quadratic travelling salesman problem (QTSP), in which a cost coefficient is associated with the transition in every vertex,…
Approximating the Incremental Knapsack Problem
Federico Della Croce, Ulrich Pferschy, Rosario Scatamacchia
We consider the 0-1 Incremental Knapsack Problem (IKP) where the capacity grows over time periods and if an item is placed in the knapsack in a certain period, it cannot be removed…
On a Stackelberg Subset Sum Game
Ulrich Pferschy, Gaia Nicosia, Andrea Pacifici
This contribution deals with a two-level discrete decision problem, a so-called Stackelberg strategic game: A Subset Sum setting is addressed with a set of items with given int…
Dynamic programming algorithms, efficient solution of the LP-relaxation and approximation schemes for the Penalized Knapsack Problem
Federico Della Croce, Ulrich Pferschy, Rosario Scatamacchia
We consider the 0-1 Penalized Knapsack Problem (PKP). Each item has a profit, a weight and a penalty and the goal is to maximize the sum of the profits minus the greatest penalty v…
The Shortest Connection Game
Andreas Darmann, Ulrich Pferschy, Joachim Schauer
We introduce Shortest Connection Game, a two-player game played on a directed graph with edge costs. Given two designated vertices in which they start, the players take turns in ch…
Generating subtour elimination constraints for the TSP from pure integer solutions
Ulrich Pferschy, Rostislav Stanek
The traveling salesman problem (TSP) is one of the most prominent combinatorial optimization problems. Given a complete graph G = (V, E) and non-negative distances d for every edge…
Price of Fairness for Allocating a Bounded Resource
Gaia Nicosia, Andrea Pacifici, Ulrich Pferschy
In this paper we study the problem of allocating a scarce resource among several players (or agents). A central decision maker wants to maximize the total utility of all agents. Ho…
On the shortest path game: extended version
Andreas Darmann, Ulrich Pferschy, Joachim Schauer
In this work we address a game theoretic variant of the shortest path problem, in which two decision makers (players) move together along the edges of a graph from a given starting…