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 2019

2019

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

Research output: Contribution to journalArticleAcademicpeer-review

Matroid
Automorphism Group
Symmetry
Trivial
Transposition

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 othersMacher, M-A., Manlove, D., Menoudakou, G., Salonen, M., Smeulders, B., 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
Practice Guidelines
Tissue Donors
Scandinavian and Nordic Countries

Column generation based math-heuristic for classification trees

Firat, M., Crognier, G., Gabor, A., Hurkens, C. A. J. & Zhang, Y., 6 Jul 2019, (Submitted) In : Computers & Operations Research. 29 p., 1810.06684v1

Research output: Contribution to journalArticleAcademicpeer-review

File
Classification Tree
Column Generation
Decision trees
Linear programming
Integer Linear Programming

Computing the chromatic number using graph decompositions via matrix rank

Jansen, B. M. P. & Nederlof, J., 7 Aug 2019, In : Theoretical Computer Science.

Research output: Contribution to journalArticleAcademicpeer-review

Graph Decomposition
Chromatic number
Decomposition
Computing
Graph in graph theory

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)Academic

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
1 Citation (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
Trees (mathematics)

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
Waiting time

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

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

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

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

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

Revealed preference theory: an algorithmic outlook

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

Research output: Contribution to journalArticleAcademicpeer-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

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

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

Research output: Contribution to journalArticleAcademicpeer-review

Tabu search
Schedule
Football
Heuristics
Transportation problem

Scheduling parallel batching machines in a sequence

Passchyn, W. & Spieksma, F. C. R., 1 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., Apr 2019, In : Annals of Operations Research. 275, 1, p. 223-243 21 p.

Research output: Contribution to journalArticleAcademicpeer-review

2018

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)

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

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)Academic

Open Access
File

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)Academic

Open Access
File

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)Academic

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
2 Citations (Scopus)

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

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

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

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

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

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)Academic

Open Access
File
1 Citation (Scopus)

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

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
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
4 Citations (Scopus)

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

New tools and connections for exponential-time approximation

Bansal, N., Chalermsook, P., Laekhanukit, B., Nanongkai, D. & Nederlof, J., 1 Jan 2018, (Accepted/In press) In : Algorithmica.

Research output: Contribution to journalArticleAcademicpeer-review

Open Access
Exponential time
Approximation algorithms
Approximation
Approximation Algorithms
Maximum Independent Set
1 Citation (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)

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

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

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

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)

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

1 Citation (Scopus)

Testing probabilistic models of choice using column generation

Smeulders, B., Davis-Stober, C., Regenwetter, M. & Spieksma, F. C. R., 1 Jul 2018, In : Computers & Operations Research. 95, p. 32-43 12 p.

Research output: Contribution to journalArticleAcademicpeer-review

Column Generation
Probabilistic Model
Weak Order
Testing
Linear Order
1 Citation (Scopus)

The gram-Schmidt walk: a cure for the banaszczyk blues

Bansal, N., Garg, S., Dadush, D. & Lovett, S., 20 Jun 2018, STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. Association for Computing Machinery, Inc, p. 1269-1282 14 p.

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

The transportation problem with conflicts

Ficker, A. M. C., Spieksma, F. C. R. & Woeginger, G. J., 21 Aug 2018, (Accepted/In press) In : Annals of Operations Research.

Research output: Contribution to journalArticleAcademicpeer-review

Transportation problem
Node
Graph
Operations research
NP-hard
2 Citations (Scopus)

Tight bounds for double coverage against weak adversaries

Bansal, N., Elias, M., Jez, L., Koumoutsos, G. & Pruhs, K., Feb 2018, In : Theory of Computing Systems. 62, 2, p. 349-365 17 p.

Research output: Contribution to journalSpecial issueAcademicpeer-review

Open Access
File
Coverage
Servers
Server
Competitive Ratio
Metric

Tighter enumeration of matroids of fixed rank

Hofstad, R. V. D., Pendavingh, R. & Pol, J. V. D., 28 Nov 2018, In : arXiv.org,e-Print Archive, Mathematics. 17 p.

Research output: Contribution to journalArticleAcademic

Open Access
File
Probabilistic Methods
Matroid
Enumeration
Counting
Encoding
2017

Algebraic matroids and Frobenius flocks

Bollen, G. P., Draisma, J. & Pendavingh, R. A., 23 Jan 2017, In : arXiv. 1701.06384v2, p. 1-21 21 p., 1701.06384v2

Research output: Contribution to journalArticleAcademic

Open Access
File
Flock
Frobenius
Matroid
Valuation
Positive Characteristic
7 Citations (Scopus)

Algorithmic discrepancy beyond partial coloring

Bansal, N. & Garg, S., 19 Jun 2017, STOC 2017 Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 19-23 June 2017, Montreal, Canada. New York: Association for Computing Machinery, Inc, p. 914-926 13 p.

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

Coloring