Meike Akveld, Raphael Bernhard (2012)
RAIRO - Theoretical Informatics and Applications
In this paper, we consider a class of scheduling problems that are among the fundamental optimization problems in operations research. More specifically, we deal with a particular version called job shop scheduling with unit length tasks. Using the results of Hromkovič, Mömke, Steinhöfel, and Widmayer presented in their work Job Shop Scheduling with Unit Length Tasks: Bounds and Algorithms, we analyze the problem setting for 2 jobs with an unequal...
Richard M. Karp (1989)
Pokroky matematiky, fyziky a astronomie
Claus-Peter Schnorr (1971)
Archiv für mathematische Logik und Grundlagenforschung
Brigitte Vallée (1989)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Phillip G. Bradford, David A. Thomas (2009)
RAIRO - Theoretical Informatics and Applications
This paper gives a shortest path algorithm for CFG (context free grammar) labeled and weighted digraphs where edge weights may be positive or negative, but negative-weight cycles are not allowed in the underlying unlabeled graph. These results build directly on an algorithm of Barrett et al. [SIAM J. Comput.30 (2000) 809–837]. In addition to many other results, they gave a shortest path algorithm for CFG labeled and weighted digraphs where all edges are nonnegative. Our algorithm is based closely...
Philippe Flajolet, Bruno Salvy, Paul Zimmermann (1989)
Publications mathématiques et informatique de Rennes
Jünger, Michael, Leipert, Sebastian (2002)
Journal of Graph Algorithms and Applications
V. Klee, P. van den Driessche (1977)
Numerische Mathematik
B. Chazelle, Herbert Edelsbrunner (1987)
Discrete & computational geometry
Manzini, Giovanni (1998)
Discrete Mathematics and Theoretical Computer Science. DMTCS [electronic only]
Y. Ke, Joseph O'Rourke (1988)
Discrete & computational geometry
Klaus Kriegel, Stephan Waack (1988)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
M. Minoux, E. Pinson (1987)
RAIRO - Operations Research - Recherche Opérationnelle
M. Smid (1992)
Discrete & computational geometry
Stefan Dobrev, Rastislav Královič, Dana Pardubská (2009)
RAIRO - Theoretical Informatics and Applications
We propose a new way of characterizing the complexity of online problems. Instead of measuring the degradation of the output quality caused by the ignorance of the future we choose to quantify the amount of additional global information needed for an online algorithm to solve the problem optimally. In our model, the algorithm cooperates with an oracle that can see the whole input. We define the advice complexity of the problem to be the minimal number of bits (normalized per input request, and...
Juraj Wiedermann (1988)
Pokroky matematiky, fyziky a astronomie
Miloslav Nekvinda (1979)
Kybernetika
Ľubomíra Dvořáková, Marie Dohnalová (2017)
Pokroky matematiky, fyziky a astronomie
V článku představíme dva druhy úloh týkajících se platby mincemi, které souvisejí s optimalitou počtu použitých mincí. V případě problému platby (říká se také rozměňování — anglicky change making problem), tj. skládání částky z mincí bez možnosti vracení, jsou úlohy spojené s optimalitou dobře prozkoumané. Analogické úlohy zformulujeme pro směnu, tj. skládání částky z mincí s možností vracení. Zde zůstává naopak řada problémů otevřená.
Goldstein, Avraham, Kolman, Petr, Zheng, Jie (2005)
The Electronic Journal of Combinatorics [electronic only]
V. Soltan, A. Gorpinevich (1993)
Discrete & computational geometry