Refine
Year of publication
Document Type
- Article (119)
- ZIB-Report (110)
- In Proceedings (38)
- Book chapter (34)
- Book (4)
- In Collection (4)
- Report (2)
- Master's Thesis (1)
Is part of the Bibliography
- no (312)
Keywords
- combinatorial optimization (4)
- integer programming (4)
- polyhedral combinatorics (4)
- BBAW (3)
- Dublin Core (3)
- Heuristics (3)
- Kooperativer Bibliotheksverbund Berlin-Brandenburg (3)
- Math-Net (3)
- column generation (3)
- polyhedra and polytopes (3)
- polynomial inequalities (3)
- Bibliotheksverbund (2)
- Harvest (2)
- Information System (2)
- Integer Programming (2)
- Internet services (2)
- KOBV (2)
- KOBV-Suchmaschine (2)
- Math-Net-Links (2)
- Online Optimization (2)
- Online-Optimierung (2)
- Open Access (2)
- Operations Research (2)
- RDF (2)
- Steiner tree (2)
- TSP (2)
- XML (2)
- distributed systems (2)
- elektronisches Publizieren (2)
- frequency assignment (2)
- line planning (2)
- online optimization (2)
- real-world problems (2)
- semi-algebraic sets (2)
- stability index (2)
- vehicle dispatching (2)
- öffentlicher Verkehr (2)
- ADAC (1)
- Algebraic Modelling Languages (1)
- Algorithmengeschichte (1)
- Algorithmus (1)
- Architektur der Suchmaschine (1)
- Asymmetric Travelling Salesman Problem (1)
- Aufzugssteuerung (1)
- Aufzugsteuerung (1)
- Automatic Storage System (1)
- Bibliothek der Zukunft (1)
- Branch&Cut-Algorithm (1)
- CEIC (1)
- Cellular Radio Telephone Systems (1)
- Column Generation (1)
- Combinatorial Auctions (1)
- Competitive Analysis (1)
- Constraint Shortest Paths Problem (1)
- Control of Stacker Cranes (1)
- Copyright (1)
- Cycles in Matroids (1)
- Discrete Mathematics (1)
- Diskrete Mathematik (1)
- Diskrete Optimierung (1)
- Dispatching von Fahrzeugen (1)
- Duty Scheduling (1)
- E-Learning (1)
- Echtzeit-Optimierung (1)
- Energy (1)
- FTTx, FTTH, FTTB, FTTC, FTTN, telecommunications, access networks, passive optical networks, network design, routing, energy efficiency (1)
- Facets (1)
- Frequency Assignment Problem (1)
- Frequenzplanung (1)
- GSM-Funknetze (1)
- Gemeinsamer Index (1)
- Gemischt-ganzzahlige Optimierung (1)
- George Dantzig (1)
- Hochschulbibliotheken (1)
- IMU (1)
- Integer Programs (1)
- KOBV-Projekt (1)
- Klassifikation (1)
- Kombinatorische Optimierung (1)
- Komplexität (1)
- Komplexitätstheorie (1)
- Kostenaufteilungsprobleme (1)
- Kürzeste Wege (1)
- Laserschweißen (1)
- MIP-Solver (1)
- Mathematics in Industry (1)
- Mathematik als Entscheidungshilfe (1)
- Mathematikunterricht in Schulen (1)
- Metadaten (1)
- Minimum-Cost Flow Problems (1)
- Mobilfunk (1)
- Modelling (1)
- Network Capacity Planning (1)
- OSPF Routing (1)
- Online Public Access Catalog (1)
- Online optimization (1)
- Online-Algorithm (1)
- Open Access Catalog (1)
- Optimierung (1)
- Optimization (1)
- P=NP (1)
- PCB Design (1)
- Packing (1)
- Produktionsfaktor Mathematik (1)
- Public transport (1)
- Publikations- und Kommunikationstechniken (1)
- Railway Slot Allocation (1)
- Realtime Optimization (1)
- Rundreisen (1)
- Shortest Path Routing (1)
- Spieltheorie (1)
- Steiner tree packing (1)
- Suchmaschine (1)
- Survey (1)
- Survivable Networks (1)
- Teaching (1)
- Telecommunication (1)
- Telecommunication Network Design (1)
- Telekommunikation (1)
- Telota (1)
- Telota-Projekt (1)
- Time Windows (1)
- Train Dispatching (1)
- Transportation (1)
- Transportation Systems (1)
- Traveling Salesman Problem (1)
- Travelling-Salesman-Problem (1)
- Verteilte Suche (1)
- Wahlverfahren und Mathematik (1)
- Wissenschaftsrat (1)
- World Digital Mathematics Library (1)
- applications in industry (1)
- applications of integer programming (1)
- applications to manufacturing (1)
- authentischer Mathematikunterricht (1)
- branch and bound (1)
- cardinality homogeneous set systems (1)
- chains (1)
- coloring (1)
- competitive analysis (1)
- competitiveness (1)
- computational complexity (1)
- cutting plane algorithm (1)
- cutting planes (1)
- digitale Bibliothek (1)
- digitale Information (1)
- digitale Informationstechnologie (1)
- digitale Informationsversorgung (1)
- discrete mathematics (1)
- discrete optimization (1)
- diskrete Mathematik (1)
- diskrete Optimierung (1)
- duty scheduling (1)
- dynamic programming (1)
- e-learning (1)
- electronic learning (1)
- elektronische Publikation (1)
- elektronisches Lehren und Lernen (1)
- elevator (1)
- elevator control (1)
- facets (1)
- ganzzahlige Programmierung (1)
- gas transport optimization (1)
- graph coloring (1)
- graph theory (1)
- greedy algorithm (1)
- hop constraints (1)
- industrial mathematics (1)
- kompetitive Analyse (1)
- mixed integer nonlinear programming (1)
- mixed-integer programs (1)
- mobile phone (1)
- operations research (1)
- optimale Tour (1)
- perfect graphs (1)
- placement (1)
- polyhedron (1)
- polytopes (1)
- pricing (1)
- public transit (1)
- public transportation (1)
- real world data (1)
- real-time (1)
- routing (1)
- routing in VLSI-design (1)
- semialgebraic sets (1)
- shortest paths (1)
- simulation studies (1)
- soft time windows (1)
- techniques of publishing and communication (1)
- telecommunication (1)
- transportation planning (1)
- traveling salesman problem (1)
- vehicle scheduling (1)
- wissenschaftliche Informationsversorgung (1)
- Öffentlicher Personenverkehr (1)
A beautiful result of Bröcker and Scheiderer on the stability index of basic closed semi-algebraic sets implies, as a very special case, that every $d$-dimensional polyhedron admits a representation as the set of solutions of at most $d(d+1)/2$ polynomial inequalities. Even in this polyhedral case, however, no constructive proof is known, even if the quadratic upper bound is replaced by any bound depending only on the dimension. Here we give, for simple polytopes, an explicit construction of polynomials describing such a polytope. The number of used polynomials is exponential in the dimension, but in the 2- and 3-dimensional case we get the expected number $d(d+1)/2$.
Combinatorial online optimization is an area with lots of applications and potential for significant progress, both in theory and practice. In this short note we sketch the ADACproblem, a typical large-scale online optimization problem, discuss some theoretical and pratical issues coming up, and explain, very briefly, how we approach this problem mathematically. Online problems are a battlefield of heuristics with many strong claims about their solution quality. We indicate that a stronger problem orientation and the use of a little more mathematics may yield.
A subset ${\cal C}$ of the power set of a finite set $E$ is called cardinality homogeneous if, whenever ${\cal C}$ contains some set $F$, ${\cal C}$ contains all subsets of $E$ of cardinality $|F|$. Examples of such set systems ${\cal C}$ are the sets of circuits and the sets of cycles of uniform matroids and the sets of all even or of all odd cardinality subsets of $E$. With each cardinality homogeneous set system ${\cal C}$, we associate the polytope $P({\cal C})$, the convex hull of the incidence vectors of all sets in ${\cal C}$, and provide a complete and nonredundant linear description of $P({\cal C})$. We show that a greedy algorithm optimizes any linear function over $P({\cal C})$, give an explicit optimum solution of the dual linear program, and provide a polynomial time separation algorithm for the class of polytopes of type $P({\cal C})$.
P=NP?
(2002)
Hinter der für den Uneingeweihten etwas kryptischen Frage "P = NP?" verbirgt sich das derzeit wichtigste Problem der Komplexitätstheorie. Dieser Artikel erläutert einige Aspekte der Theorie und erklärt informell, was "P = NP?" bedeutet. Es geht nicht nur um komplizierte algorithmische Mathematik und Informatik, sondern um grundsätzliche Fragen unserer Lebensumwelt. Kann man vielleicht beweisen, dass es für viele Probleme unseres Alltags keine effizienten Lösungsmethoden gibt?
Optimization is the task of finding an optimum solution to a given problem. When the decision variables are discrete we speak of a combinatorial optimization problem. Such a problem is online when decisions have to be made before all data of the problem are known. And we speak of a real-time online problem when online decisions have to be computed within very tight time bounds. This paper surveys the are of combinatorial online and real-time optimization, it discusses, in particular, the concepts with which online and real-time algorithms can be analyzed.
This paper discusses online optimization of real-world transportation systems. We concentrate on transportation problems arising in production and manufacturing processes, in particular in company internal logistics. We describe basic techniques to design online optimization algorithms for such systems, but our main focus is decision support for the planner: which online algorithm is the most appropriate one in a particular setting? We show by means of several examples that traditional methods for the evaluation of online algorithms often do not suffice to judge the strengths and weaknesses of online algorithms. We present modifications of well-known evaluation techniques and some new methods, and we argue that the selection of an online algorithm to be employed in practice should be based on a sound combination of several theoretical and practical evaluation criteria, including simulation.
Das \emph{Committee on Electronic Information and Communication} (CEIC) der \emph{International Mathematical Union} (IMU) hat die Aufgabe, sich über die langfristige Informationsversorgung in der Mathematik Gedanken zu machen und Lösungsvorschläge hierfür zu erarbeiten. Das Kernthema ist natürlich "`Elektronisches Publizieren"'. Dazu gehören auch Copyright-Regelungen. % Sie sind -- % neben einer Andeutung der weiteren CEIC-Pläne -- der Fokus dieses % kurzen Artikels. Er schließt mit einem von der IMU verabschiedeten % Aufruf zu vernünftigem Verhalten bei Copyright-Vereinbarungen. Eine % nachhaltige Befolgung dieses Aufrufs -- verbunden mit weiteren % Aktivitäten -- könnte die (derzeit kaum noch bezahlbare und % dadurch gefährdete) Literaturversorgung nachhaltig zum Positiven % verändern. Mit diesem Artikel beginnt eine kleine Serie von Aufsätzen, in denen ich (in meiner Funktion als eines von elf CEIC-Mitgliedern) die Empfehlungen des CEIC erläutern werde. % Das heutige Thema sind die % CEIC-Vorschläge zum Copyright
We present an approach to implement an auction of railway slots. Railway network, train driving characteristics, and safety requirements are described by a simplified, but still complex macroscopic model. In this environment, slots are modelled as combinations of scheduled track segments. The auction design builds on the iterative combinatorial auction. However, combinatorial bids are restricted to some types of slot bundles that realize positive synergies between slots. We present a bidding language that allows bidding for these slot bundles. An integer programming approach is proposed to solve the winner determination problem of our auction. Computational results for auction simulations in the Hannover-Fulda-Kassel area of the German railway network give evidence that auction approaches can induce a more efficient use of railway capacity.
Our main result is that every $n$-dimensional polytope can be described by at most $2n-1$ polynomial inequalities and, moreover, these polynomials can explicitly be constructed. For an $n$-dimensional pointed polyhedral cone we prove the bound $2n-2$ and for arbitrary polyhedra we get a constructible representation by $2n$ polynomial inequalities.
The line planning problem is one of the fundamental problems in strategic planning of public and rail transport. It consists in finding lines and corresponding frequencies in a transport network such that a given travel demand can be satisfied. There are (at least) two objectives. The transport company wishes to minimize operating costs, the passengers want to minimize travel times. We propose a n ew multi-commodity flow model for line planning. Its main features, in comparison to existing models, are that the passenger paths can be freely routed and that the lines are generated dynamically. We discuss properties of this model and investigate its complexity. Results with data for the city of Potsdam, Germany, are reported.