Combinatorial Optimization

  • PO Box 513, Department of Mathematics and Computer Science

    5600 MB Eindhoven

    Netherlands

  • Groene Loper 5, MetaForum

    5612 AP Eindhoven

    Netherlands

Research Output 1988 2020

2020
47 Downloads (Pure)

Column generation based heuristic for learning classification trees

Firat, M., Crognier, G., Gabor, A. F., Hurkens, C. A. J. & Zhang, Y., Apr 2020, In : Computers & Operations Research. 116, 11 p., 104866.

Research output: Contribution to journalArticleAcademicpeer-review

Classification Tree
Column Generation
Decision trees
Linear programming
Integer Linear Programming

Practical combinatorial optimization

Spieksma, F. C. R., 21 Feb 2020, (Accepted/In press) Eindhoven: Technische Universiteit Eindhoven.

Research output: Book/ReportInaugural speechProfessional

2 Citations (Scopus)

The transportation problem with conflicts

Ficker, A. M. C., Spieksma, F. C. R. & Woeginger, G. J., 2020, In : Annals of Operations Research.

Research output: Contribution to journalArticleAcademicpeer-review

Transportation problem
Node
Graph
Approximation algorithms
Factors
2019
1 Downloads (Pure)

Asymptotics of symmetry in matroids

Pendavingh, R. & van der Pol, J., 1 Mar 2019, In : Journal of Combinatorial Theory, Series B. 135, p. 349-365 17 p.

Research output: Contribution to journalArticleAcademicpeer-review

Matroid
Automorphism Group
Symmetry
Trivial
Transposition
2 Citations (Scopus)
20 Downloads (Pure)

Building Kidney Exchange Programmes in Europe: an overview of exchange practice and activities

Biro, P., Haase-Kromwijk, B., Andersson, T., Ásgeirsson, E., Baltesová, T., Boletis, I., Bolotinha, C., Bond, G., Böhmig, G., Burnapp, L., Cechlárová, K., Di Caccio, P., Fronek, J., Hadaya, K., Hemke, A., Jacquelinet, C., Johnson, R., Kieszek, R., Kuypers, D., Leisman, R. & 10 others, Macher, M-A., Manlove, D., Menoudakou, G., Salonen, M., Smeulders, B. M. L., Sparacino, V., Spieksma, F. C. R., de la Oliva Valentín Muñoz, M., Wilson, N. & van de Klundert, J., 1 Jul 2019, In : Transplantation. 103, 7, p. 1514-1522 9 p.

Research output: Contribution to journalArticleAcademicpeer-review

Open Access
File
Kidney
Living Donors
Transplants
Practice Guidelines
Tissue Donors

Computing the chromatic number using graph decompositions via matrix rank

Jansen, B. M. P. & Nederlof, J., 26 Nov 2019, In : Theoretical Computer Science. 795, p. 520-539 20 p.

Research output: Contribution to journalArticleAcademicpeer-review

Graph Decomposition
Chromatic number
Decomposition
Computing
Graph in graph theory
3 Downloads (Pure)

Equal-subset-sum faster than the meet-in-the-middle

Mucha, M., Nederlof, J., Pawlewicz, J. & Węgrzycki, K., Sep 2019, 27th Annual European Symposium on Algorithms, ESA 2019. Bender, M. A., Svensson, O. & Herman, G. (eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 16 p. 73. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 144).

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Open Access
File
Polynomials
Set theory
Computational complexity
3 Downloads (Pure)

Hamiltonicity below Dirac's condition

Jansen, B. M. P., Kozma, L. & Nederlof, J., 2019, In : arXiv. 14 p., 1902.01745v1.

Research output: Contribution to journalArticleAcademic

Open Access
File
Hamiltonicity
Vertex Degree
Paul Adrien Maurice Dirac
Hamiltonian circuit
Tractability

Hamiltonicity below Dirac’s condition

Jansen, B. M. P., Kozma, L. & Nederlof, J., 12 Sep 2019, Graph-Theoretic Concepts in Computer Science - 45th International Workshop, WG 2019, Revised Papers. Sau, I. & Thilikos, D. M. (eds.). Cham: Springer, p. 27-39 13 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 11789 LNCS).

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Hamiltonians
Hamiltonicity
Graph theory
Parameterization
Paul Adrien Maurice Dirac
131 Downloads (Pure)

High-tech low-volume production planning

de Kruijff, J. T., 5 Jul 2019, Eindhoven: Technische Universiteit Eindhoven. 134 p.

Research output: ThesisPhd Thesis 1 (Research TU/e / Graduation TU/e)

Open Access
File

Modelling and optimisation in European Kidney Exchange Programmes

Biró, P., van de Klundert, J., Manlove, D., Pettersson, W., Andersson, T., Burnapp, L., Chromy, P., Delgado, P., Dworczak, P., Haase, B., Hemke, A., Johnson, R., Klimentova, X., Kuypers, D., Nanni Costa, A., Smeulders, B., Spieksma, F. C. R., Valentín, M. O. & Viana, A., 7 Sep 2019, In : European Journal of Operational Research.

Research output: Contribution to journalArticleAcademicpeer-review

Open Access
Kidney
Optimization
Modeling
Operations research
Synthesis
2 Citations (Scopus)

Nearly ETH-tight algorithms for planar Steiner Tree with terminals on few faces

Kisfaludi-Bak, S., Nederlof, J. & van Leeuwen, E. J., 2019, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms. Chan, T. M. (ed.). New York: Association for Computing Machinery, Inc, p. 1015-1034 20 p.

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Open Access
Steiner Tree
Face
Graph in graph theory
Steiner Tree Problem
K-space

No-wait scheduling for locks

Passchyn, W., Briskorn, D. & Spieksma, F. C. R., 2019, In : INFORMS Journal on Computing. 31, 3, p. 413-428 16 p.

Research output: Contribution to journalArticleAcademicpeer-review

Scheduling
Dynamic programming
No-wait
Graph
Schedule

On a generalization of iterated and randomized rounding

Bansal, N., 23 Jun 2019, STOC 2019 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. Charikar, M. & Cohen, E. (eds.). New York: Association for Computing Machinery, Inc, p. 1125-1135 11 p.

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

4 Downloads (Pure)

On geometric set cover for orthants

Bringmann, K., Kisfaludi-Bak, S., Pilipczuk, M. & van Leeuwen, E. J., 1 Sep 2019, 27th Annual European Symposium on Algorithms, ESA 2019. Bender, M. A., Svensson, O. & Herman, G. (eds.). Dagstuhl: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 18 p. 26. (Leibniz International Proceedings in Informatics (LIPIcs); vol. 144).

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Open Access
File
Approximation algorithms
Multiobjective optimization
Polynomials
14 Downloads (Pure)

Online interval scheduling on two related machines: the power of lookahead

Pinson, N. & Spieksma, F. C. R., 15 Jul 2019, In : Journal of Combinatorial Optimization. 38, 1, p. 224-253 30 p.

Research output: Contribution to journalArticleAcademicpeer-review

Open Access
File
Look-ahead
Arrival Time
Scheduling
Unit of length
Distinct

On the discrepancy of random low degree set systems

Bansal, N. & Meka, R., 2019, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms. Chan, T. M. (ed.). New York: Association for Computing Machinery, Inc, p. 2557-2564 8 p.

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Open Access
Set Systems
Coloring
Discrepancy
Random Systems
Random Sets
5 Downloads (Pure)

Perfect matroids over hyperfields

Bowler, N. & Pendavingh, R. A., 9 Aug 2019, In : arXiv.org,e-Print Archive, Mathematics. 16 p., 1908.03420vl.

Research output: Contribution to journalArticleAcademic

Open Access
File
Matroid
Axioms
Skew
Oriented Matroid
Valued Fields
1 Downloads (Pure)

Revealed preference theory: an algorithmic outlook

Smeulders, B. M. L., Crama, Y. & Spieksma, F. C. R., 1 Feb 2019, In : European Journal of Operational Research. 272, 3, p. 803-815 13 p.

Research output: Contribution to journalReview articleAcademicpeer-review

Revealed Preference
Operations research
Economics
Operations Research
Testing

Revenue maximization in an optical router node using multiple wavelengths

Abidini, M. A., Boxma, O., Hurkens, C., Koonen, T. & Resing, J., 12 Mar 2019, Proceedings of the 12th EAI International Conference on Performance Evaluation Methodologies and Tools, VALUETOOLS 2019. Association for Computing Machinery, Inc, p. 47-53 7 p.

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Routers
Wavelength
Bins
Linear programming
Profitability
2 Citations (Scopus)

Scheduling a non-professional indoor football league: a tabu search based approach

Van Bulck, D., Goossens, D. R. & Spieksma, F. C. R., 15 Apr 2019, In : Annals of Operations Research. 275, 2, p. 715-730 16 p.

Research output: Contribution to journalArticleAcademicpeer-review

Football
Tabu search
Schedule
Heuristics
Transportation problem

Scheduling parallel batching machines in a sequence

Passchyn, W. & Spieksma, F. C. R., 15 Jun 2019, In : Journal of Scheduling. 22, 3, p. 335-357 23 p.

Research output: Contribution to journalArticleAcademicpeer-review

Computational complexity
Scheduling
Hardness
Polynomials
Batching

The sport teams grouping problem

Toffolo, T. A. M., Christiaens, J., Spieksma, F. C. R. & Vanden Berghe, G., 1 Apr 2019, In : Annals of Operations Research. 275, 1, p. 223-243 21 p.

Research output: Contribution to journalArticleAcademicpeer-review

2018
1 Citation (Scopus)

Achievable performance of blind policies in heavy traffic

Bansal, N., Kamphorst, B. & Zwart, B., 1 Aug 2018, In : Mathematics of Operations Research. 43, 3, p. 949-964 16 p.

Research output: Contribution to journalArticleAcademicpeer-review

Heavy Traffic
Applied Probability
Competitive Analysis
Sojourn Time
Queue

A column generation approach for the shift design and rostering problem in airport ground handling

Firat, M., van Twist, J. & Hurkens, C. A. J., 8 Jul 2018.

Research output: Contribution to conferenceAbstractAcademic

Airports
Personnel
Costs
Preferred numbers
Planning
1 Citation (Scopus)
46 Downloads (Pure)

Algebraic matroids and Frobenius flocks

Bollen, G. P., Draisma, J. & Pendavingh, R., 7 Jan 2018, In : Advances in Mathematics. 323, p. 688-719 32 p.

Research output: Contribution to journalArticleAcademicpeer-review

Open Access
File
Flock
Frobenius
Matroid
Valuation
Positive Characteristic
55 Downloads (Pure)

Algorithms for combinatorial discrepancy

Garg, S., 10 Oct 2018, Eindhoven: Technische Universiteit Eindhoven. 139 p.

Research output: ThesisPhd Thesis 1 (Research TU/e / Graduation TU/e)

Open Access
File
438 Downloads (Pure)

Algorithms for k-server problems

Koumoutsos, G., 6 Sep 2018, Eindhoven: Technische Universiteit Eindhoven. 91 p.

Research output: ThesisPhd Thesis 1 (Research TU/e / Graduation TU/e)

Open Access
File
133 Downloads (Pure)

Algorithms for some metrical service systems

Elias, M., 17 Sep 2018, Eindhoven: Technische Universiteit Eindhoven. 90 p.

Research output: ThesisPhd Thesis 1 (Research TU/e / Graduation TU/e)

Open Access
File
2 Citations (Scopus)

A tight lower bound for counting Hamiltonian cycles via matrix rank

Curticapean, R., Lindze, N. & Nederlof, J., 1 Jan 2018, 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018. New York: Association for Computing Machinery, Inc, p. 1080-1099 20 p.

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Open Access
Hamiltonians
Hamiltonian circuit
Counting
Lower bound
Exponential time
4 Citations (Scopus)
47 Downloads (Pure)

Competitive algorithms for generalized k-server in uniform metrics.

Bansal, N., Elias, M., Koumoutsos, G. & Nederlof, J., 2018, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 7-10 January 2018, New Orleans, Louisiana. s.l.: Society for Industrial and Applied Mathematics (SIAM), p. 992-1001

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Open Access
File
Servers
Polynomials
2 Downloads (Pure)

Computing the chromatic number using graph decompositions via matrix rank

Jansen, B. M. P. & Nederlof, J., 2018, In : arXiv. 29 p., 1806.10501v1.

Research output: Contribution to journalArticleAcademic

Open Access
File
Coloring
Decomposition
Parameterization
Separators
Combinatorial optimization
13 Downloads (Pure)

Computing the chromatic number using graph decompositions via matrix rank

Jansen, B. M. P. & Nederlof, J., 1 Aug 2018, 26th European Symposium on Algorithms, ESA 2018. Bast, H., Herman, G. & Azar, Y. (eds.). Wadern: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 15 p. 47. (Leibniz International Proceedings in Informatics (LIPIcs); vol. 112).

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Open Access
File
Decomposition
Parameterization
Separators
Coloring
Combinatorial optimization
1 Citation (Scopus)

Faster space-efficient algorithms for subset sum, k -sum, and related problems

Bansal, N., Garg, S., Nederlof, J. & Vyas, N., 1 Jan 2018, In : SIAM Journal on Computing. 47, 5, p. 1755-1777 23 p.

Research output: Contribution to journalArticleAcademicpeer-review

Subset Sum
Set theory
Efficient Algorithms
Polynomials
Integer programming
91 Downloads (Pure)

Fast Hamiltonicity checking via bases of perfect matchings

Cygan, M., Kratsch, S. & Nederlof, J., 13 Mar 2018, In : Journal of the ACM. 65, 3, p. 1-46

Research output: Contribution to journalArticleAcademicpeer-review

Open Access
File
Hamiltonians
Factorization
Directed graphs
Decomposition
72 Downloads (Pure)

Field extensions, derivations, and matroids over skew hyperfields

Pendavingh, R., 7 Feb 2018, In : arXiv. 1802.02447.

Research output: Contribution to journalArticleAcademic

Open Access
File
Field extension
Matroid
Skew
Positive Characteristic
Duality Theorems
143 Downloads (Pure)

Frobenius flocks and algebraicity of matroids

Bollen, G. P., 7 Dec 2018, Eindhoven: Technische Universiteit Eindhoven. 156 p.

Research output: ThesisPhd Thesis 1 (Research TU/e / Graduation TU/e)

Open Access
File
3 Citations (Scopus)
93 Downloads (Pure)

Integer programming models for mid-term production planning for high-tech low-volume supply chains

de Kruijff, J. T., Hurkens, C. A. J. & de Kok, A. G., 16 Sep 2018, In : European Journal of Operational Research. 269, 3, p. 984-997 14 p.

Research output: Contribution to journalArticleAcademicpeer-review

File
Production Planning
Integer programming
Integer Programming
Supply Chain
Supply chains
2 Citations (Scopus)

More consequences of falsifying SETH and the orthogonal vectors conjecture

Abboud, A., Dell, H., Bringmann, K. & Nederlof, J., 20 Jun 2018, STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. New York: Association for Computing Machinery, Inc, p. 445-456 12 p.

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Hardness
Networks (circuits)
Polynomials
Wire
32 Downloads (Pure)

More consequences of falsifying SETH and the orthogonal vectors conjecture

Abboud, A., Bringmann, K., Dell, H. & Nederlof, J., 22 May 2018, In : arXiv. 1805.08554.

Research output: Contribution to journalArticleAcademic

Open Access
File
Clique
Hardness
Exhaustive Search
Exponential time
Randomized Algorithms
5 Citations (Scopus)
67 Downloads (Pure)

Nested convex bodies are chaseable.

Bansal, N., Bohm, M., Elias, M., Koumoutsos, G. & Umboh, S. W., 2018, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 7-10 January 2018, New Orleans, Louisiana. s.l.: Society for Industrial and Applied Mathematics (SIAM), p. 1253-1260

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Open Access
File
Convex Body
Competitive Ratio
Linear Constraints
Lower bound
Minimise
4 Downloads (Pure)

New tools and connections for exponential-time approximation

Bansal, N., Chalermsook, P., Laekhanukit, B., Nanongkai, D. & Nederlof, J., 1 Jan 2018, In : Algorithmica. 81, 10, p. 3993-4009

Research output: Contribution to journalArticleAcademicpeer-review

Open Access
File
Exponential time
Approximation algorithms
Approximation
Approximation Algorithms
Maximum Independent Set
2 Citations (Scopus)

On directed feedback vertex set parameterized by treewidth

Bonamy, M., Kowalik, Ł., Nederlof, J., Pilipczuk, M., Socała, A. & Wrochna, M., 1 Jan 2018, Graph-Theoretic Concepts in Computer Science - 44th International Workshop, WG 2018, Proceedings. Brandstädt, A., Köhler, E. & Meer, K. (eds.). Springer, p. 65-78 14 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 11159 LNCS).

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Feedback Vertex Set
Treewidth
Directed graphs
Dynamic programming
Feedback
1 Citation (Scopus)

On the Lovász Theta function for independent sets in sparse graphs

Bansal, N., Gupta, A. & Guruganesh, G., 1 Jan 2018, In : SIAM Journal on Computing. 47, 3, p. 1039-1055 17 p.

Research output: Contribution to journalArticleAcademicpeer-review

Sparse Graphs
Integrality
Theta Functions
Coloring
Independent Set
1 Citation (Scopus)
15 Downloads (Pure)

On the number of bases of almost all matroids

Pendavingh, R. & van der Pol, J., 1 Aug 2018, In : Combinatorica. 38, 4 , p. 955–985 31 p.

Research output: Contribution to journalArticleAcademicpeer-review

Open Access
File
Matroid
Girth
Truncation
Minor
Cardinality
8 Downloads (Pure)

Packing sporadic real-time tasks on identical multiprocessor systems

Chen, J. J., Bansal, N., Chakraborty, S. & Von Der Brüggen, G., 1 Dec 2018, 29th International Symposium on Algorithms and Computation, ISAAC 2018. Lee, D-T., Liao, C-S. & Hsu, W-L. (eds.). Dagstuhl: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 14 p. 71. (Leibniz International Proceedings in Informatics (LIPIcs); vol. 123).

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Open Access
File
Real time systems
Polynomials
Scheduling
7 Downloads (Pure)

Partitioning vectors into quadruples: Worst-case analysis of a matching-based algorithm

Ficker, A. M. C., Erlebach, T., Mihalák, M. & Spieksma, F. C. R., 1 Dec 2018, Partitioning Vectors into Quadruples: Worst-Case Analysis of a Matching-Based Algorithm. Hsu, W-L., Lee, D-T. & Liao, C-S. (eds.). Wadern: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 12 p. 45. (Leibniz International Proceedings in Informatics (LIPIcs); vol. 123).

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Open Access
File
Approximation algorithms
Costs
26 Downloads (Pure)

Revenue maximization in an optical router node using multiple wavelengths

Abidini, M. A., Boxma, O., Hurkens, C., Koonen, T. & Resing, J., 15 Sep 2018, In : arXiv. 2018, 1809.07860 , 6 p., 1809.07860 .

Research output: Contribution to journalArticleAcademic

Open Access
File
Routers
Wavelength
1 Citation (Scopus)
2 Downloads (Pure)

Robust balanced optimization

Ficker, A. M. C., Spieksma, F. C. R. & Woeginger, G., 2018, In : EURO Journal on Computational Optimization. 6, 3, p. 239-266

Research output: Contribution to journalArticleAcademicpeer-review

Optimization
Optimization Problem
Costs
Assignment Problem
Subset
1 Citation (Scopus)

Sharper upper bounds for unbalanced uniquely decodable code pairs

Austrin, P., Kaski, P., Koivisto, M. & Nederlof, J., 1 Feb 2018, In : IEEE Transactions on Information Theory. 64, 2, p. 1368-1373 6 p., 7888502.

Research output: Contribution to journalArticleAcademicpeer-review