Gerhard J. Woeginger

According to our database1, Gerhard J. Woeginger
  • authored at least 424 papers between 1988 and 2017.
  • has a "Dijkstra number"2 of three.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2017
The one-dimensional Euclidean domain: finitely many obstructions are not enough.
Social Choice and Welfare, 2017

Partitioning Perfect Graphs into Stars.
Journal of Graph Theory, 2017

The Dominating Set Problem in Geometric Intersection Graphs.
CoRR, 2017

Scheduling Two Agents on a Single Machine: A Parameterized Analysis of NP-hard Problems.
CoRR, 2017

Dynamic and Kinetic Conflict-Free Coloring of Intervals with Respect to Points.
CoRR, 2017

The Subset Sum Game Revisited.
Proceedings of the Algorithmic Decision Theory - 5th International Conference, 2017

2016
Finding large degree-anonymous subgraphs is hard.
Theor. Comput. Sci., 2016

Are there any nicely structured preference profiles nearby?
Mathematical Social Sciences, 2016

Linearizable special cases of the QAP.
J. Comb. Optim., 2016

Bilevel Knapsack with Interdiction Constraints.
INFORMS Journal on Computing, 2016

The triangle scheduling problem.
CoRR, 2016

The multi-stripe travelling salesman problem.
CoRR, 2016

Precedence-constrained scheduling problems parameterized by partial order width.
CoRR, 2016

Fine-Grained Complexity Analysis of Two Classic TSP Variants.
CoRR, 2016

The Focus of Attention Problem.
Algorithmica, 2016

Vertex Cover Meets Scheduling.
Algorithmica, 2016

Balanced Optimization with Vector Costs.
Proceedings of the Approximation and Online Algorithms - 14th International Workshop, 2016

Fine-Grained Complexity Analysis of Two Classic TSP Variants.
Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

Precedence-Constrained Scheduling Problems Parameterized by Partial Order Width.
Proceedings of the Discrete Optimization and Operations Research, 2016

2015
How to Put Through Your Agenda in Collective Binary Decisions.
ACM Trans. Economics and Comput., 2015

Network-Based Vertex Dissolution.
SIAM J. Discrete Math., 2015

Vote trading and subset sums.
Oper. Res. Lett., 2015

Preface.
Math. Program., 2015

Approximability and parameterized complexity of multicover by c-intervals.
Inf. Process. Lett., 2015

Geometric versions of the three-dimensional assignment problem under general norms.
Discrete Optimization, 2015

Well-solvable cases of the QAP with block-structured matrices.
Discrete Applied Mathematics, 2015

The one-dimensional Euclidean domain: Finitely many obstructions are not enough.
CoRR, 2015

Are there any nicely structured preference~profiles~nearby?
CoRR, 2015

The (Weighted) Metric Dimension of Graphs: Hard and Easy Cases.
Algorithmica, 2015

Scheduling Two Competing Agents When One Agent Has Significantly Fewer Jobs.
Proceedings of the 10th International Symposium on Parameterized and Exact Computation, 2015

A New Tractable Case of the QAP with a Robinson Matrix.
Proceedings of the Combinatorial Optimization and Applications, 2015

2014
A Study on the Computational Complexity of the Bilevel Knapsack Problem.
SIAM Journal on Optimization, 2014

Two hardness results for Gamson's game.
Social Choice and Welfare, 2014

Bilevel programming and the separation problem.
Math. Program., 2014

Investigations on the step-based research indices of Chambers and Miller.
J. Informetrics, 2014

A Multivariate Complexity Analysis of Lobbying in Multiple Referenda.
J. Artif. Intell. Res., 2014

Four-point conditions for the TSP: The complete complexity classification.
Discrete Optimization, 2014

Group Activity Selection Problem.
CoRR, 2014

Geometric versions of the 3-dimensional assignment problem under general norms.
CoRR, 2014

Planar 3-dimensional assignment problems with Monge-like cost arrays.
CoRR, 2014

Linearizable special cases of the QAP.
CoRR, 2014

Parameterized Algorithmics for Computational Social Choice: Nine Research Challenges.
CoRR, 2014

Network-Based Dissolution.
CoRR, 2014

Star Partitions of Perfect Graphs.
CoRR, 2014

Multiprocessor Jobs, Preemptive Schedules, and One-Competitive Online Algorithms.
Proceedings of the Approximation and Online Algorithms - 12th International Workshop, 2014

Network-Based Dissolution.
Proceedings of the Mathematical Foundations of Computer Science 2014, 2014

Star Partitions of Perfect Graphs.
Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

Another Look at the Shoelace TSP: The Case of Very Old Shoes.
Proceedings of the Fun with Algorithms - 7th International Conference, 2014

2013
Nothing New about Equiangular Polygons.
The American Mathematical Monthly, 2013

A characterization of the single-crossing domain.
Social Choice and Welfare, 2013

Uniqueness in quadratic and hyperbolic 0-1 programming problems.
Oper. Res. Lett., 2013

Motion Planning with Pulley, Rope, and Baskets.
Theory Comput. Syst., 2013

A hardness result for core stability in additive hedonic games.
Mathematical Social Sciences, 2013

Analysis of multi-stage open shop processing systems.
Math. Program., 2013

The three-dimensional matching problem in Kalmanson matrices.
J. Comb. Optim., 2013

Fully decomposable split graphs.
Eur. J. Comb., 2013

Two hardness results for core stability in hedonic coalition formation games.
Discrete Applied Mathematics, 2013

Uniqueness in quadratic and hyperbolic 0-1 programming problems.
CoRR, 2013

Realizing Small Tournaments Through Few Permutations.
Acta Cybern., 2013

Complexity and in-approximability of a selection problem in robust optimization.
4OR, 2013

Core Stability in Hedonic Coalition Formation.
Proceedings of the SOFSEM 2013: Theory and Practice of Computer Science, 2013

The Complexity of Finding a Large Subgraph under Anonymity Constraints.
Proceedings of the Algorithms and Computation - 24th International Symposium, 2013

A Complexity and Approximability Study of the Bilevel Knapsack Problem.
Proceedings of the Integer Programming and Combinatorial Optimization, 2013

Are There Any Nicely Structured Preference Profiles Nearby?
Proceedings of the IJCAI 2013, 2013

How to Put through Your Agenda in Collective Binary Decisions.
Proceedings of the Algorithmic Decision Theory - Third International Conference, 2013

2012
An algorithmic analysis of the Honey-Bee game.
Theor. Comput. Sci., 2012

The Alcuin Number of a Graph and Its Connections to the Vertex Cover Number.
SIAM Review, 2012

Scheduling of pipelined operator graphs.
J. Scheduling, 2012

Another well-solvable case of the QAP: Maximizing the job completion time variance.
Oper. Res. Lett., 2012

Complexity and approximation of an area packing problem.
Optimization Letters, 2012

Between a rock and a hard place: the two-to-one assignment problem.
Math. Meth. of OR, 2012

Guest Editorial to the special issue "Operations Research in Health Care" (EURO XXIII, July 5-8, 2009, Bonn).
European Journal of Operational Research, 2012

The x-and-y-axes travelling salesman problem.
European Journal of Operational Research, 2012

The interval ordering problem.
Discrete Applied Mathematics, 2012

Core stability in hedonic coalition formation
CoRR, 2012

Caching Is Hard - Even in the Fault Model.
Algorithmica, 2012

An algorithmic study of switch graphs.
Acta Inf., 2012

Group Activity Selection Problem.
Proceedings of the Internet and Network Economics - 8th International Workshop, 2012

The (Weighted) Metric Dimension of Graphs: Hard and Easy Cases.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2012

Motion planning with pulley, rope, and baskets.
Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science, 2012

Transportation under Nasty Side Constraints.
Proceedings of the Mathematical Foundations of Computer Science 2012, 2012

Cinderella versus the Wicked Stepmother.
Proceedings of the Theoretical Computer Science, 2012

Divorcing Made Easy.
Proceedings of the Fun with Algorithms - 6th International Conference, 2012

2011
Analysis of the dial-a-ride problem of Hunsaker and Savelsbergh.
Oper. Res. Lett., 2011

A well-solvable special case of the bounded knapsack problem.
Oper. Res. Lett., 2011

Graph coloring with rejection.
J. Comput. Syst. Sci., 2011

Charlemagne's Challenge: The Periodic Latency Problem.
Operations Research, 2011

Unbounded knapsack problems with arithmetic weight sequences.
European Journal of Operational Research, 2011

The Wiener maximum quadratic assignment problem.
Discrete Optimization, 2011

Hamiltonian index is NP-complete.
Discrete Applied Mathematics, 2011

The Northwest corner rule revisited.
Discrete Applied Mathematics, 2011

Paths, trees and matchings under disjunctive constraints.
Discrete Applied Mathematics, 2011

The interval ordering problem
CoRR, 2011

Analysis of multi-stage open shop processing systems
CoRR, 2011

An Algorithmic Analysis of the Honey-Bee Game
CoRR, 2011

String execution time for finite languages: Max is easy, min is hard.
Automatica, 2011

The Cinderella Game on Holes and Anti-holes.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2011

Analysis of multi-stage open shop processing systems.
Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science, 2011

Reachability and Deadlocking Problems in Multi-stage Scheduling.
Proceedings of the Reachability Problems - 5th International Workshop, 2011

Unweighted Coalitional Manipulation under the Borda Rule Is NP-Hard.
Proceedings of the IJCAI 2011, 2011

Domination When the Stars Are Out.
Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

Two-Bounded-Space Bin Packing Revisited.
Proceedings of the Algorithms - ESA 2011, 2011

2010
The Alcuin Number of a Graph and Its Connections to the Vertex Cover Number.
SIAM J. Discrete Math., 2010

Parallel machine scheduling with nested job assignment restrictions.
Oper. Res. Lett., 2010

How * not * to solve a Sudoku.
Oper. Res. Lett., 2010

The approximability of three-dimensional assignment problems with bottleneck objective.
Optimization Letters, 2010

Pinpointing the complexity of the interval min-max regret knapsack problem.
Discrete Optimization, 2010

Domination When the Stars Are Out
CoRR, 2010

The Traveling Salesman Problem Under Squared Euclidean Distances
CoRR, 2010

An Algorithmic Comparison of Three Scientific Impact Indices.
Acta Cybern., 2010

The Traveling Salesman Problem under Squared Euclidean Distances.
Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science, 2010

The Focus of Attention Problem.
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

An Algorithmic Analysis of the Honey-Bee Game.
Proceedings of the Fun with Algorithms, 5th International Conference, 2010

Caching Is Hard - Even in the Fault Model.
Proceedings of the Algorithms, 2010

2009
Partitioning graphs into connected parts.
Theor. Comput. Sci., 2009

How hard is it to find extreme Nash equilibria in network congestion games?
Theor. Comput. Sci., 2009

A new family of scientific impact measures: The generalized Kosmulski-indices.
Scientometrics, 2009

The hardness of train rearrangements.
Oper. Res. Lett., 2009

Threshold aggregation of multi-graded rankings.
Mathematical Social Sciences, 2009

The complexity of computing the Muirhead-Dalton distance.
Mathematical Social Sciences, 2009

Generalizations of Egghe's g-index.
JASIST, 2009

A comment on parallel-machine scheduling under a grade of service provision to minimize makespan.
Inf. Process. Lett., 2009

Timetabling problems at the TU Eindhoven.
European Journal of Operational Research, 2009

Uncapacitated single and multiple allocation p-hub center problems.
Computers & OR, 2009

Polygons with inscribed circles and prescribed side lengths.
Appl. Math. Lett., 2009

An Algorithmic Study of Switch Graphs.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2009

Between a Rock and a Hard Place: The Two-to-One Assignment Problem.
Proceedings of the Approximation and Online Algorithms, 7th International Workshop, 2009

Fully Decomposable Split Graphs.
Proceedings of the Combinatorial Algorithms, 20th International Workshop, 2009

Partitioning Graphs into Connected Parts.
Proceedings of the Computer Science, 2009

Combinatorial Optimization Problems with Conflict Graphs.
Proceedings of the 8th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, 2009

2008
Getting the best response for your erg.
ACM Trans. Algorithms, 2008

Multigraph realizations of degree sequences: Maximization is easy, minimization is hard.
Oper. Res. Lett., 2008

The computational complexity of graph contractions II: Two tough polynomially solvable cases.
Networks, 2008

The computational complexity of graph contractions I: Polynomially solvable and NP-complete cases.
Networks, 2008

An axiomatic characterization of the Hirsch-index.
Mathematical Social Sciences, 2008

An axiomatic analysis of Egghe's g-index.
J. Informetrics, 2008

A symmetry axiom for scientific impact indices.
J. Informetrics, 2008

Tight bounds for break minimization in tournament scheduling.
J. Comb. Theory, Ser. A, 2008

The Magnus-Derek game revisited.
Inf. Process. Lett., 2008

The problem of the moody chess players.
Inf. Process. Lett., 2008

Four Non-Deterministic Programming Exercises.
Bulletin of the EATCS, 2008

The Freudenthal Problem and its Ramifications (Part III).
Bulletin of the EATCS, 2008

Open problems around exact algorithms.
Discrete Applied Mathematics, 2008

2-piercings via graph theory.
Discrete Applied Mathematics, 2008

How Hard Is It to Find Extreme Nash Equilibria in Network Congestion Games?
Proceedings of the Internet and Network Economics, 4th International Workshop, 2008

The Alcuin Number of a Graph.
Proceedings of the Algorithms, 2008

2007
Approximation schemes for a class of subset selection problems.
Theor. Comput. Sci., 2007

Preface.
Theor. Comput. Sci., 2007

Complexity of the job insertion problem in multi-stage scheduling.
Oper. Res. Lett., 2007

Quadratic programming and combinatorial minimum weight product problems.
Math. Program., 2007

Backbone colorings for graphs: Tree and path backbones.
Journal of Graph Theory, 2007

Steiner diagrams and k-star hubs.
J. Discrete Algorithms, 2007

Roll cutting in the curtain industry, or: A well-solvable allocation problem.
European Journal of Operational Research, 2007

The Freudenthal Problem and its Ramifications (Part II).
Bulletin of the EATCS, 2007

On the complexity of cake cutting.
Discrete Optimization, 2007

A polynomial time equivalence between DNA sequencing and the exact perfect matching problem.
Discrete Optimization, 2007

Eliminating graphs by means of parallel knock-out schemes.
Discrete Applied Mathematics, 2007

An Approximation Scheme For Cake Division With A Linear Number Of Cuts.
Combinatorica, 2007

Very Large-Scale Neighborhoods with Performance Guarantees for Minimizing Makespan on Parallel Machines.
Proceedings of the Approximation and Online Algorithms, 5th International Workshop, 2007

2006
On the robust assignment problem under a fixed number of cost scenarios.
Oper. Res. Lett., 2006

Exact algorithms for the Hamiltonian cycle problem in planar graphs.
Oper. Res. Lett., 2006

The traveling salesman problem with few inner points.
Oper. Res. Lett., 2006

Scheduling with step-improving processing times.
Oper. Res. Lett., 2006

The constrained minimum weighted sum of job completion times problem.
Math. Program., 2006

A Note on Fair Division under Interval Uncertainty.
International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 2006

On the dimension of simple monotonic games.
European Journal of Operational Research, 2006

Performance of a Very Large-Scale Neighborhood for Minimizing Makespan on Parallel Machines.
Electronic Notes in Discrete Mathematics, 2006

Timetabling problems at the TU Eindhoven.
Electronic Notes in Discrete Mathematics, 2006

Some Problems around Traveling Salesmen, Dart Boards, and Euro-coins.
Bulletin of the EATCS, 2006

The Freudenthal Problem and its Ramifications (Part I).
Bulletin of the EATCS, 2006

Sports tournaments, home-away assignments, and the break minimization problem.
Discrete Optimization, 2006

Well-solvable instances for the partition problem.
Appl. Math. Lett., 2006

Planar Graph Coloring Avoiding Monochromatic Subgraphs: Trees and Paths Make It Difficult.
Algorithmica, 2006

Four point conditions and exponential neighborhoods for symmetric TSP.
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

Timetabling Problems at the TU Eindhoven.
Proceedings of the Practice and Theory of Automated Timetabling VI, 2006

Graph Coloring with Rejection.
Proceedings of the Algorithms, 2006

Quadratic Programming and Combinatorial Minimum Weight Product Problems.
Proceedings of the Algorithms and Complexity, 6th Italian Conference, 2006

2005
Graph colorings.
Theor. Comput. Sci., 2005

Combinatorial approximation algorithms: a comparative review.
Oper. Res. Lett., 2005

The no-wait flow-shop paradox.
Oper. Res. Lett., 2005

Approximation of the supply scheduling problem.
Oper. Res. Lett., 2005

Faster algorithms for computing power indices in weighted voting games.
Mathematical Social Sciences, 2005

The two-dimensional cutting stock problem revisited.
Math. Program., 2005

Complexity and Approximability of Double Digest.
J. Bioinformatics and Computational Biology, 2005

A comment on scheduling two parallel machines with capacity constraints.
Discrete Optimization, 2005

Decomposition of integer matrices and multileaf collimator sequencing.
Discrete Applied Mathematics, 2005

Minimizing Makespan and Preemption Costs on a System of Uniform Machines.
Algorithmica, 2005

Paths and cycles in colored graphs.
Australasian J. Combinatorics, 2005

A Note on Semi-online Machine Covering.
Proceedings of the Approximation and Online Algorithms, Third International Workshop, 2005

Roll Cutting in the Curtain Industry.
Proceedings of the Algorithms, 2005

Two Remarks on Reconstructing Binary Vectors from Their Absorbed Projections.
Proceedings of the Discrete Geometry for Computer Imagery, 12th International Conference, 2005

05301 Abstracts Collection - Exact Algorithms and Fixed-Parameter Tractability.
Proceedings of the Exact Algorithms and Fixed-Parameter Tractability, 24.-27. July 2005, 2005

05301 Summary - Exact Algorithms and Fixed-Parameter Tractability.
Proceedings of the Exact Algorithms and Fixed-Parameter Tractability, 24.-27. July 2005, 2005

2004
Seventeen lines and one-hundred-and-one points.
Theor. Comput. Sci., 2004

It is tough to be a plumber.
Theor. Comput. Sci., 2004

Radio Labeling with Preassigned Frequencies.
SIAM Journal on Optimization, 2004

Inapproximability results for no-wait job shop scheduling.
Oper. Res. Lett., 2004

On the nearest neighbor rule for the traveling salesman problem.
Oper. Res. Lett., 2004

Minimum-cost dynamic flows: The series-parallel case.
Networks, 2004

All-norm approximation algorithms.
J. Algorithms, 2004

Project scheduling with irregular costs: complexity, approximability, and algorithms.
Acta Inf., 2004

Exact (Exponential) Algorithms for the Dominating Set Problem.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2004

The Computational Complexity of the Minimum Weight Processor Assignment Problem.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2004

Getting the Best Response for Your Erg.
Proceedings of the Algorithm Theory, 2004

Parallel Knock-Out Schemes in Networks.
Proceedings of the Mathematical Foundations of Computer Science 2004, 2004

Approximation Schemes for a Class of Subset Selection Problems.
Proceedings of the LATIN 2004: Theoretical Informatics, 2004

Space and Time Complexity of Exact Algorithms: Some Open Problems (Invited Talk).
Proceedings of the Parameterized and Exact Computation, First International Workshop, 2004

The Constrained Minimum Weighted Sum of Job Completion Times Problem.
Proceedings of the Integer Programming and Combinatorial Optimization, 2004

The Traveling Salesman Problem with Few Inner Points.
Proceedings of the Computing and Combinatorics, 10th Annual International Conference, 2004

Approximation Schemes for Broadcasting in Heterogenous Networks.
Proceedings of the Approximation, 2004

2003
On tiling under tomographic constraints.
Theor. Comput. Sci., 2003

Random Redundant Storage in Disk Arrays: Complexity of Retrieval Problems.
IEEE Trans. Computers, 2003

Banks winners in tournaments are difficult to recognize.
Social Choice and Welfare, 2003

Local search for the minimum label spanning tree problem with bounded color classes.
Oper. Res. Lett., 2003

The two-machine open shop problem: To fit or not to fit, that is the question.
Oper. Res. Lett., 2003

A note on scoring rules that respect majority in choice and elimination.
Mathematical Social Sciences, 2003

Preemptive scheduling with rejection.
Math. Program., 2003

A note on the complexity of determining optimal strategies in games with common payoffs.
Math. Meth. of OR, 2003

The geometric maximum traveling salesman problem.
J. ACM, 2003

The complexity of economic equilibria for house allocation markets.
Inf. Process. Lett., 2003

How to detect a counterfeit coin: Adaptive versus non-adaptive solutions.
Inf. Process. Lett., 2003

Complexity and approximability results for slicing floorplan designs.
European Journal of Operational Research, 2003

Preface: Volume 13.
Electronic Notes in Discrete Mathematics, 2003

On the approximability of average completion time scheduling under precedence constraints.
Discrete Applied Mathematics, 2003

Recognizing DNA graphs is difficult.
Discrete Applied Mathematics, 2003

Which matrices are immune against the transportation paradox?
Discrete Applied Mathematics, 2003

The post correspondence problem over a unary alphabet.
Appl. Math. Lett., 2003

The Complexity of Graph Contractions.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2003

Backbone Colorings for Networks.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2003

A Faster FPT Algorithm for Finding Spanning Trees with Many Leaves.
Proceedings of the Mathematical Foundations of Computer Science 2003, 2003

Seventeen Lines and One-Hundred-and-One Points.
Proceedings of the Algorithms, 2003

A Lower Bound for Cake Cutting.
Proceedings of the Algorithms, 2003

Double Digest Revisited: Complexity and Approximability in the Presence of Noisy Data.
Proceedings of the Computing and Combinatorics, 9th Annual International Conference, 2003

2002
Off-line temporary tasks assignment.
Theor. Comput. Sci., 2002

Solution of a problem in DNA computing.
Theor. Comput. Sci., 2002

Squares from Products of Consecutive Integers.
The American Mathematical Monthly, 2002

Embeddings of planar graphs that minimize the number of long-face cycles.
Oper. Res. Lett., 2002

An efficient algorithm for a class of constraint satisfaction problems.
Oper. Res. Lett., 2002

The quadratic 0-1 knapsack problem with series-parallel support.
Oper. Res. Lett., 2002

On-line scheduling of unit time jobs with rejection: minimizing the total completion time.
Oper. Res. Lett., 2002

The mathematics of playing golf, or: a new class of difficult non-linear mixed integer programs.
Math. Program., 2002

Resource augmentation for online bounded space bin packing.
J. Algorithms, 2002

A faster off-line algorithm for the TCP acknowledgement problem.
Inf. Process. Lett., 2002

Approximation Algorithms for Scheduling Malleable Tasks Under Precedence Constraints.
Int. J. Found. Comput. Sci., 2002

Open problems in the theory of scheduling.
Bulletin of the EATCS, 2002

The Geometric Maximum Traveling Salesman Problem
CoRR, 2002

Some Comments on Sequencing with Controllable Processing Times.
Computing, 2002

More About Subcolorings.
Computing, 2002

The complexity of multiple wordlength assignment.
Appl. Math. Lett., 2002

Caching for Web Searching.
Algorithmica, 2002

A PTAS for single machine scheduling with controllable processing times.
Acta Cybern., 2002

More about Subcolorings.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2002

DNA Sequencing, Eulerian Graphs, and the Exact Perfect Matching Problem.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2002

Planar Graph Coloring with Forbidden Subgraphs: Why Trees and Paths Are Dangerous.
Proceedings of the Algorithm Theory, 2002

All-Norm Approximation Algorithms.
Proceedings of the Algorithm Theory, 2002

The mathematics of playing golf.
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

How to cut a cake almost fairly.
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

Project Scheduling with Irregular Costs: Complexity, Approximability, and Algorithms.
Proceedings of the Algorithms and Computation, 13th International Symposium, 2002

An Approximation Scheme for Cake Division with a Linear Number of Cuts.
Proceedings of the Algorithms, 2002

Minimizing Makespan and Preemption Costs on a System of Uniform Machines.
Proceedings of the Algorithms, 2002

Radio Labeling with Pre-assigned Frequencies.
Proceedings of the Algorithms, 2002

2001
A polynomially solvable special case of the unbounded knapsack problem.
Oper. Res. Lett., 2001

A very difficult scheduling problem with communication delays.
Oper. Res. Lett., 2001

A comment on consecutive-2-out-of-n systems.
Oper. Res. Lett., 2001

Hardness of approximation of the discrete time-cost tradeoff problem.
Oper. Res. Lett., 2001

The reconstruction of polyominoes from their orthogonal projections.
Inf. Process. Lett., 2001

Non-Approximability Results for Scheduling Problems with Minsum Criteria.
INFORMS Journal on Computing, 2001

Resource augmentation for online bounded space bin packing
Electronic Colloquium on Computational Complexity (ECCC), 2001

When does a dynamic programming formulation guarantee the existence of an FPTAS?
Electronic Colloquium on Computational Complexity (ECCC), 2001

A note on the depth function of combinatorial optimization problems.
Discrete Applied Mathematics, 2001

Linear time approximation scheme for the multiprocessor open shop problem.
Discrete Applied Mathematics, 2001

A Note on Tiling under Tomographic Constraints
CoRR, 2001

The complexity of coloring graphs without long induced paths.
Acta Cybern., 2001

De Bruijn Graphs and DNA Graphs.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2001

Complexity of Coloring Graphs without Forbidden Induced Subgraphs.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2001

Assigning chain-like tasks to a chain-like network.
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

On the Approximability of Average Completion Time Scheduling under Precedence Constraints.
Proceedings of the Automata, Languages and Programming, 28th International Colloquium, 2001

The Buffer Minimization Problem for Multiprocessor Scheduling with Conflicts.
Proceedings of the Automata, Languages and Programming, 28th International Colloquium, 2001

Approximation Algorithms for Scheduling Malleable Tasks under Precedence Constraints.
Proceedings of the Algorithms, 2001

Buying a Constant Competitive Ratio for Paging.
Proceedings of the Algorithms, 2001

Exact Algorithms for NP-Hard Problems: A Survey.
Proceedings of the Combinatorial Optimization, 2001

2000
A polynomial time approximation scheme for the two-stage multiprocessor flow shop problem.
Theor. Comput. Sci., 2000

A comment on scheduling on uniform machines under chain-type precedence constraints.
Oper. Res. Lett., 2000

Monge strikes again: optimal placement of web proxies in the internet.
Oper. Res. Lett., 2000

Semi-online scheduling with decreasing job sizes.
Oper. Res. Lett., 2000

On-line scheduling on a single machine: maximizing the number of early jobs.
Oper. Res. Lett., 2000

A study of exponential neighborhoods for the Travelling Salesman Problem and for the Quadratic Assignment Problem.
Math. Program., 2000

A PTAS for Minimizing the Total Weighted Completion Time on Identical Parallel Machines.
Math. Oper. Res., 2000

When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)?
INFORMS Journal on Computing, 2000

On the Complexity of Function Learning
Electronic Colloquium on Computational Complexity (ECCC), 2000

The Maximum Travelling Salesman Problem on Symmetric Demidenko Matrices.
Discrete Applied Mathematics, 2000

Introduction.
Algorithmica, 2000

Pseudo-Hamiltonian Graphs.
Acta Cybern., 2000

Caching for Web Searching.
Proceedings of the Algorithm Theory, 2000

Scheduling a pipelined operator graph.
Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

Resource Augmentation for Online Bounded Space Bin Packing.
Proceedings of the Automata, Languages and Programming, 27th International Colloquium, 2000

Approximability and in-approximability results for no-wait shop scheduling.
Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

Preemptive Scheduling with Rejection.
Proceedings of the Algorithms, 2000

1999
Approximability and Nonapproximability Results for Minimizing Total Flow Time on a Single Machine.
SIAM J. Comput., 1999

Optimal on-line algorithms for variable-sized bin covering.
Oper. Res. Lett., 1999

Approximation algorithms for the multiprocessor open shop scheduling problem.
Oper. Res. Lett., 1999

A linear-time algorithm for the bottleneck transportation problem with a fixed number of sources.
Oper. Res. Lett., 1999

A note on the bottleneck graph partition problem.
Networks, 1999

Minimum-cost strong network orientation problems: Classification, complexity, and algorithms.
Networks, 1999

Erratum: The Travelling Salesman and the PQ-Tree.
Math. Oper. Res., 1999

A note on the complexity of the transportation problem with a permutable demand vector.
Math. Meth. of OR, 1999

The Steiner Tree Problem in Kalmanson Matrices and in Circulant Matrices.
J. Comb. Optim., 1999

An Approximation Scheme for Minimizing Agreeably Weighted Variance on a Single Machine.
INFORMS Journal on Computing, 1999

Sensitivity Analysis for Knapsack Problems: Another Negative Result.
Discrete Applied Mathematics, 1999

On-Line Scheduling on a Single Machine: Minimizing the Total Completion Time.
Acta Inf., 1999

A PTAS for Minimizing the Weighted Sum of Job Completion Times on Parallel Machines.
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

When Does a Dynamic Programming Formulation Guarantee the Existence of an FPTAS?
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

Preemptive Scheduling with Job-Dependent Setup Times.
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

Randomized Online Scheduling on Two Uniform Machines.
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

An FPTAS for Agreeably Weighted Variance on a Single Machine.
Proceedings of the Automata, 1999

1998
Well-Solvable Special Cases of the Traveling Salesman Problem: A Survey.
SIAM Review, 1998

Sometimes Travelling is Easy: The Master Tour Problem.
SIAM J. Discrete Math., 1998

A comment on a minmax location problem.
Oper. Res. Lett., 1998

One, two, three, many, or: complexity aspects of dynamic network flows with dedicated arcs.
Oper. Res. Lett., 1998

A solvable case of the quadratic assignment problem.
Oper. Res. Lett., 1998

Sequencing jobs that require common resources on a single machine: A solvable case of the TSP.
Math. Program., 1998

Makespan minimization in open shops: A polynomial time approximation scheme.
Math. Program., 1998

The quadratic assignment problem with a monotone anti-Monge and a symmetric Toeplitz matrix: Easy and hard cases.
Math. Program., 1998

The Travelling Salesman and the PQ-Tree.
Math. Oper. Res., 1998

On-Line Scheduling of Two-Machine Open Shops Where Jobs Arrive Over Time.
J. Comb. Optim., 1998

The Travelling Salesman Problem on Permuted Monge Matrices.
J. Comb. Optim., 1998

The Stock Size Problem.
Operations Research, 1998

The toughness of split graphs.
Discrete Mathematics, 1998

Makespan Minimization in Preemptive Two Machine Job Shops.
Computing, 1998

On-Line and Off-Line Approximation Algorithms for Vector Covering Problems.
Algorithmica, 1998

Minimizing the Number of Tardy Jobs on a Single Machine with Batch Setup Times.
Acta Cybern., 1998

Non-approximability Results for Scheduling Problems with Minsum Criteria.
Proceedings of the Integer Programming and Combinatorial Optimization, 1998

The Maximum Traveling Salesman Problem Under Polyhedral Norms.
Proceedings of the Integer Programming and Combinatorial Optimization, 1998

1997
A polynomial-time approximation scheme for maximizing the minimum machine completion time.
Oper. Res. Lett., 1997

Minimizing the total completion time in a unit-time open shop with release times.
Oper. Res. Lett., 1997

Greedy Algorithms for On-Line Data Compression.
J. Algorithms, 1997

There is no Asymptotic PTAS for Two-Dimensional Vector Packing.
Inf. Process. Lett., 1997

Shelf Algorithms for On-Line Strip Packing.
Inf. Process. Lett., 1997

Hamiltonian cycles in circulant digraphs with two stripes.
Discrete Mathematics, 1997

Simple But Efficient Approaches for the Collapsing Knapsack Problem.
Discrete Applied Mathematics, 1997

The VC-dimension of Set Systems Defined by Graphs.
Discrete Applied Mathematics, 1997

Unit-Time Scheduling Problems with Time Dependent Resources.
Computing, 1997

Angle-Restricted Tours in the Plane.
Comput. Geom., 1997

Pseudo-Hamiltonian Graphs.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 1997

Approximation Schemes for Scheduling.
Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997

1996
The Convex-Hull-and-k-Line Travelling Salesman Problem.
Inf. Process. Lett., 1996

Three-dimensional Axial Assignment Problems with Decomposable Cost Coefficients.
Discrete Applied Mathematics, 1996

The Fractional Greedy Algorithm for Data Compression.
Computing, 1996

On the Recognition of Permuted Supnick and Incomplete Monge Matrices.
Acta Inf., 1996

One, Two, Three, Many, or: Complexity Aspects of Dynamic Network Flows with Dedicated Arcs.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 1996

Approximability and Nonapproximability Results for Minimizing Total Flow Time on a Single Machine.
Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996

The Travelling Salesman and the PQ-Tree.
Proceedings of the Integer Programming and Combinatorial Optimization, 1996

The Quadratic Assignment Problem with a Monotone Anti-Monge and a Symmetric Toeplitz Matrix: Easy and Hard Cases.
Proceedings of the Integer Programming and Combinatorial Optimization, 1996

On-line and Off-line Approximation Algorithms for Vector Covering Problems.
Proceedings of the Algorithms, 1996

Competitive Odds and Ends.
Proceedings of the Online Algorithms, 1996

Competitive Analysis of Algorithms.
Proceedings of the Online Algorithms, 1996

On-line Packing and Covering Problems.
Proceedings of the Online Algorithms, 1996

1995
An optimal algorithm for preemptive on-line scheduling.
Oper. Res. Lett., 1995

On the rate of taxation in a cooperative bin packing game.
Math. Meth. of OR, 1995

The cone of Monge matrices: Extremal rays and applications.
Math. Meth. of OR, 1995

Minimizing the weighted number of late jobs in UET open shops.
Math. Meth. of OR, 1995

On-line bin packing - A restricted survey.
Math. Meth. of OR, 1995

On the Complexity of Function Learning.
Machine Learning, 1995

Scheduling with Time-Dependent Execution Times.
Inf. Process. Lett., 1995

Counting Convex Polygons in Planar Point Sets.
Inf. Process. Lett., 1995

on the Recognition of Permuted Bottleneck Monge Matrices.
Discrete Applied Mathematics, 1995

Permuting Matrices to Avoid Forbidden Submatrices.
Discrete Applied Mathematics, 1995

UET-scheduling with chain-type precedence constraints.
Computers & OR, 1995

VC-Dimensions for Graphs (Extended Abstract).
Proceedings of the Graph-Theoretic Concepts in Computer Science, 1995

Minimum Cost Dynamic Flows: The Series-Parallel Case.
Proceedings of the Integer Programming and Combinatorial Optimization, 1995

Sometimes Travelling is Easy: The Master Tour Problem.
Proceedings of the Algorithms, 1995

A New Efficiently Solvable Special Case of the Three-Dimensional Axial Bottleneck Assignment Problem.
Proceedings of the Combinatorics and Computer Science, 1995

Worst-Case Analysis for On-Line Data Compression.
Proceedings of the Combinatorics and Computer Science, 1995

1994
On-Line Scheduling of Jobs with Fixed Start and End Times.
Theor. Comput. Sci., 1994

Monge matrices make maximization manageable.
Oper. Res. Lett., 1994

New lower and upper bounds for on-line scheduling.
Oper. Res. Lett., 1994

Fast algorithms for the maximum convolution problem.
Oper. Res. Lett., 1994

Some Geometric Clustering Problems.
Nord. J. Comput., 1994

A Lower Bound for Randomized On-Line Scheduling Algorithms.
Inf. Process. Lett., 1994

Scheduling with Incompatible Jobs.
Discrete Applied Mathematics, 1994

A general approach to avoiding two by two submatrices.
Computing, 1994

Partitioning Graphs into Two Trees.
Acta Cybern., 1994

Heuristics for Parallel Machine Scheduling with Delivery Times.
Acta Inf., 1994

An Optimal Algorithm for Preemptive On-line Scheduling.
Proceedings of the Algorithms, 1994

1993
Improved Space for Bounded-Space, On-Line Bin-Packing.
SIAM J. Discrete Math., 1993

An On-Line Scheduling Heuristic With Better Worst Case Ratio Than Graham's List Scheduling.
SIAM J. Comput., 1993

Drawing Graphs in the Plane with High Resolution.
SIAM J. Comput., 1993

Reconstructing sets of orthogonal line segments in the plane.
Discrete Mathematics, 1993

A Tight Bound for 3-Partitioning.
Discrete Applied Mathematics, 1993

On the Euclidean two Paths Problem.
Discrete Applied Mathematics, 1993

A Greedy-heuristic for 3-partitioning with similar elements.
Computing, 1993

Repacking helps in bounded space on-line bind-packing.
Computing, 1993

The Complexity of Detecting Crossingfree Configurations in the Plane.
BIT, 1993

A Lower Bound for On-Line Vector-Packing Algorithms.
Acta Cybern., 1993

Computing the optimum stock size.
Proceedings of the 3rd Integer Programming and Combinatorial Optimization Conference, Erice, Italy, April 29, 1993

Maximum Covering with D Cliques.
Proceedings of the Fundamentals of Computation Theory, 9th International Symposium, 1993

On the Recognition of Permuted Bottleneck Monge Matrices.
Proceedings of the Algorithms - ESA '93, First Annual European Symposium, Bad Honnef, Germany, September 30, 1993

On the Complexity of Function Learning.
Proceedings of the Sixth Annual ACM Conference on Computational Learning Theory, 1993

1992
The Complexity of Detecting Crossingfree Configurations in the Plane
Universität Trier, Mathematik/Informatik, Forschungsbericht, 1992

The Disjoint Cliques Problem
Universität Trier, Mathematik/Informatik, Forschungsbericht, 1992

Scheduling with Incompatible Jobs
Universität Trier, Mathematik/Informatik, Forschungsbericht, 1992

On the Equal-Subset-Sum Problem.
Inf. Process. Lett., 1992

The Complexity of Finding Arborescences in Hypergraphs.
Inf. Process. Lett., 1992

Finding the Closest Extreme Vertex to a Fixed Point.
Inf. Process. Lett., 1992

Counting Convex k-Gons in Planar Point Sets.
Inf. Process. Lett., 1992

Detecting Cycles Through Three Fixed Vertices in a Graph.
Inf. Process. Lett., 1992

Almost Tight Bounds for epsilon-Nets.
Discrete & Computational Geometry, 1992

Finding Minimum Area k-gons.
Discrete & Computational Geometry, 1992

Polynomial graph-colorings.
Discrete Applied Mathematics, 1992

UET-scheduling with constrained processor allocations.
Computers & OR, 1992

A heuristic for preemptive scheduling with set-up times.
Computing, 1992

Minimum-Link Paths Among Obstacles in the Plan.
Algorithmica, 1992

Computing Maximum Valued Regions.
Acta Cybern., 1992

Scheduling with Incompatible Jobs.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 1992

1991
Geometric Clusterings.
J. Algorithms, 1991

On Minimizing the Sum of k Tardinesses.
Inf. Process. Lett., 1991

Counting k-Subsets and Convex k-gons in the Plane.
Inf. Process. Lett., 1991

1990
A Simple Solution to the Two Paths Problem in Planar Graphs.
Inf. Process. Lett., 1990

On the reconstruction of simple polygons.
Bulletin of the EATCS, 1990

Drawing Graphs in the Plane with High Resolution
Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

Some New Bounds for Epsilon-Nets.
Proceedings of the Sixth Annual Symposium on Computational Geometry, 1990

Minimum-Link Paths Among Obstacles in the Plane.
Proceedings of the Sixth Annual Symposium on Computational Geometry, 1990

1989
Polynomial Graph-Colorings.
Proceedings of the STACS 89, 1989

1988
Epsilon-Nets for Halfplanes.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 1988


  Loading...