Filtern
Fachbereich / Organisatorische Einheit
- Fachbereich Mathematik (38)
- Fraunhofer (ITWM) (3)
Erscheinungsjahr
Dokumenttyp
- Preprint (41) (entfernen)
Schlagworte
- Mathematikunterricht (2)
- Modellierung (2)
- hub location (2)
- integer programming (2)
- integer programming (2)
- network flows (2)
- optimization (2)
- praxisorientiert (2)
- valid inequalities (2)
- Algorithmics (1)
-
Some Complexity Results for k-Cardinality Minimum Cut Problems
(2000)
- Many polynomially solvable combinatorial optimization problems (COP) become NP when we require solutions to satisfy an additional cardinality constraint. This family of problems has been considered only recently. We study a newproblem of this family: the k-cardinality minimum cut problem. Given an undirected edge-weighted graph the k-cardinality minimum cut problem is to find a partition of the vertex set V in two sets V 1 , V 2 such that the number of the edges between V 1 and V 2 is exactly k and the sum of the weights of these edges is minimal. A variant of this problem is the k-cardinality minimum s-t cut problem where s and t are fixed vertices and we have the additional request that s belongs to V 1 and t belongs to V 2 . We also consider other variants where the number of edges of the cut is constrained to be either less or greater than k. For all these problems we show complexity results in the most significant graph classes.
-
Multifacility Location Problems with Tree Structure and Finite Dominating Sets
(2018)
- Multifacility location problems arise in many real world applications. Often, the facilities can only be placed in feasible regions such as development or industrial areas. In this paper we show the existence of a finite dominating set (FDS) for the planar multifacility location problem with polyhedral gauges as distance functions, and polyhedral feasible regions, if the interacting facilities form a tree. As application we show how to solve the planar 2-hub location problem in polynomial time. This approach will yield an ε-approximation for the euclidean norm case polynomial in the input data and 1/ε.
-
Multicriteria network location problems with sumb objectives
(1999)
- In this paper network location problems with several objectives are discussed, where every single objective is a classical median objective function. We will lock at the problem of finding Pareto optimal locations and lexicographically optimal locations. It is shown that for Pareto optimal locations in undirected networks no node dominance result can be shown. Structural results as well as efficient algorithms for these multi-criteria problems are developed. In the special case of a tree network a generalization of Goldman's dominance algorithm for finding Pareto locations is presented.
-
A Finite Dominating Set Algorithm for a Dynamic Location Problem in the Plane
(2014)
- A single facility problem in the plane is considered, where an optimal location has to be identified for each of finitely many time-steps with respect to time-dependent weights and demand points. It is shown that the median objective can be reduced to a special case of the static multifacility median problem such that results from the latter can be used to tackle the dynamic location problem. When using block norms as distance measure between facilities, a Finite Dominating Set (FDS) is derived. For the special case with only two time-steps, the resulting algorithm is analyzed with respect to its worst-case complexity. Due to the relation between dynamic location problems for T time periods and T-facility problems, this algorithm can also be applied to the static 2-facility location problem.
-
Algorithms for Time-Dependent Bicriteria Shortest Path Problems (revised version)
(2004)
- In this paper we generalize the classical shortest path problem in two ways. We consider two objective functions and time-dependent data. The resulting problem, called the time-dependent bicriteria shortest path problem (TdBiSP), has several interesting practical applications, but has not gained much attention in the literature.
-
Algorithms for Time Dependent Bicriteria Shortest Path Problems
(2003)
- We generalize the classical shortest path problem in two ways. We consider two - in general contradicting - objective functions and introduce a time dependency of the cost which is caused by a traversal time on each arc. The resulting problem, called time-dependent bicriteria shortest path problem (TdBiSP) has several interesting practical applications, but has not attained much attention in the literature.
-
Earliest Arrival Flows with Time-Dependent Data
(2003)
- In this paper we discuss an earliest arrival flow problem of a network having arc travel times and capacities that vary with time over a finite time horizon T. We also consider the possibility to wait (or park) at a node before departingon outgoing arc. This waiting is bounded by the value of maximum waiting time and the node capacity which also vary with time.
-
Classification of Location Problems
(1999)
- There are several good reasons to introduce classification schemes for optimization problems including, for instance, the ability for concise problem statement opposed to verbal, often ambiguous, descriptions or simple data encoding and information retrieval in bibliographical information systems or software libraries. In some branches like scheduling and queuing theory classification is therefore a widely accepted and appreciated tool. The aim of this paper is to propose a 5-position classification which can be used to cover all location problems. We will provide a list of currentliy available symbols and indicate its usefulness in a - necessarily non-comprehensive - list of classical location problems. The classification scheme is in use since 1992 and has since proved to be useful in research, software development, classroom, and for overview articles.
-
Bicriteria approach to the optimal location of surveillance cameras
(2014)
- We consider the problem of finding efficient locations of surveillance cameras, where we distinguish between two different problems. In the first, the whole area must be monitored and the number of cameras should be as small as possible. In the second, the goal is to maximize the monitored area for a fixed number of cameras. In both of these problems, restrictions on the ability of the cameras, like limited depth of view or range of vision are taken into account. We present solution approaches for these problems and report on results of their implementations applied to an authentic problem. We also consider a bicriteria problem with two objectives: maximizing the monitored area and minimizing the number of cameras, and solve it for our study case.
-
Bicriteria approach to the optimal location of surveillance cameras
(2014)
- We consider the problem of finding efficient locations of surveillance cameras, where we distinguish between two different problems. In the first, the whole area must be monitored and the number of cameras should be as small as possible. In the second, the goal is to maximize the monitored area for a fixed number of cameras. In both of these problems, restrictions on the ability of the cameras, like limited depth of view or range of vision are taken into account. We present solution approaches for these problems and report on results of their implementations applied to an authentic problem. We also consider a bicriteria problem with two objectives: maximizing the monitored area and minimizing the number of cameras, and solve it for our study case.
