Monaldo Mastrolilli

János Barta

Stefano Gualandi

Discret. Optim., 2025

Branch-And-Bound Algorithms as Polynomial-Time Approximation Schemes.

[BibT_eX]

[DOI]

Koppány István Encz

Proceedings of the 52nd International Colloquium on Automata, Languages, and Programming, 2025

On the Degree Automatability of Sum-Of-Squares Proofs.

[BibT_eX]

[DOI]

Alex Bortolotti

Luis Felipe Vargas

Proceedings of the 52nd International Colloquium on Automata, Languages, and Programming, 2025

2024

Tight Sum-of-squares Lower Bounds for Binary Polynomial2 Optimization Problems.

[BibT_eX]

[DOI]

Ambrogio Maria Bernardelli

ACM Trans. Comput. Theory, March, 2024

On the integrality gap of the Complete Metric Steiner Tree Problem via a novel formulation.

[BibT_eX]

[DOI]

Stefano Gualandi

CoRR, 2024

2023

On the generation of metric TSP instances with a large integrality gap by branch-and-cut.

[BibT_eX]

[DOI]

Stefano Gualandi

Math. Program. Comput., June, 2023

2022

Ideal Membership Problem over 3-Element CSPs with Dual Discriminator Polymorphism.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., September, 2022

On inequalities with bounded coefficients and pitch for the min knapsack polytope.

[BibT_eX]

[DOI]

Discret. Optim., 2022

2021

Ideal Membership Problem for Boolean Minority and Dual Discriminator.

[BibT_eX]

[DOI]

Proceedings of the 46th International Symposium on Mathematical Foundations of Computer Science, 2021

2020

Ideal Membership Problem for Boolean Minority.

[BibT_eX]

[DOI]

CoRR, 2020

Ideal Membership Problem and a Majority Polymorphism over the Ternary Domain.

[BibT_eX]

[DOI]

Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science, 2020

2019

The Complexity of the Ideal Membership Problem and Theta Bodies for Constrained Problems Over the Boolean Domain.

[BibT_eX]

[DOI]

CoRR, 2019

The Complexity of the Ideal Membership Problem for Constrained Problems Over the Boolean Domain.

[BibT_eX]

[DOI]

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

2018

On Bounded Pitch Inequalities for the Min-Knapsack Polytope.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Optimization - 5th International Symposium, 2018

2017

An unbounded Sum-of-Squares hierarchy integrality gap for a polynomially solvable problem.

[BibT_eX]

[DOI]

Math. Program., 2017

On the Hardest Problem Formulations for the 0/1 Lasserre Hierarchy.

[BibT_eX]

[DOI]

Math. Oper. Res., 2017

High Degree Sum of Squares Proofs, Bienstock-Zuckerberg hierarchy and Chvatal-Gomory cuts.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2017

High Degree Sum of Squares Proofs, Bienstock-Zuckerberg Hierarchy and CG Cuts.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatorial Optimization, 2017

2016

Sum-of-Squares Rank Upper Bounds for Matching Problems.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Optimization - 4th International Symposium, 2016

Semidefinite and Linear Programming Integrality Gaps for Scheduling Identical Machines.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatorial Optimization, 2016

Sum-of-Squares Hierarchy Lower Bounds for Symmetric Formulations.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatorial Optimization, 2016

Tight Sum-Of-Squares Lower Bounds for Binary Polynomial Optimization Problems.

[BibT_eX]

[DOI]

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

2015

On the Hardest Problem Formulations for the 0/1 0 / 1 Lasserre Hierarchy.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

A Lasserre Lower Bound for the Min-Sum Single Machine Scheduling Problem.

[BibT_eX]

[DOI]

Proceedings of the Algorithms - ESA 2015, 2015

2014

Bi-criteria and approximation algorithms for restricted matchings.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2014

On the Lasserre/Sum-of-Squares Hierarchy with Knapsack Covering Inequalities.

[BibT_eX]

[DOI]

CoRR, 2014

Improved Approximation for the Maximum Duo-Preservation String Mapping Problem.

[BibT_eX]

[DOI]

Proceedings of the Algorithms in Bioinformatics - 14th International Workshop, 2014

2013

Single machine scheduling with scenarios.

[BibT_eX]

[DOI]

Nikolaus Mutsanas

Theor. Comput. Sci., 2013

On the approximation of minimum cost homomorphism to bipartite graphs.

[BibT_eX]

[DOI]

Arash Rafiey

Discret. Appl. Math., 2013

Lasserre Integrality Gaps for Certain Capacitated Covering Problems.

[BibT_eX]

[DOI]

CoRR, 2013

How to Sell Hyperedges: The Hypermatching Assignment Problem.

[BibT_eX]

[DOI]

Marek Cygan

Fabrizio Grandoni

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

2012

Competitive-Ratio Approximation Schemes for Makespan Scheduling Problems.

[BibT_eX]

[DOI]

Proceedings of the Approximation and Online Algorithms - 10th International Workshop, 2012

The Feedback Arc Set Problem with Triangle Inequality Is a Vertex Cover Problem.

[BibT_eX]

[DOI]

Proceedings of the LATIN 2012: Theoretical Informatics, 2012

Constrained Matching Problems in Bipartite Graphs.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Optimization - Second International Symposium, 2012

Approximation of Minimum Cost Homomorphisms.

[BibT_eX]

[DOI]

Pavol Hell

Mayssam Mohammadi Nevisi

Arash Rafiey

Proceedings of the Algorithms - ESA 2012, 2012

Restricted Max-Min Fair Allocations with Inclusion-Free Intervals.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics - 18th Annual International Conference, 2012

2011

Inapproximability Results for Maximum Edge Biclique, Minimum Linear Arrangement, and Sparsest Cut.

[BibT_eX]

[DOI]

SIAM J. Comput., 2011

On the Approximability of Single-Machine Scheduling with Precedence Constraints.

[BibT_eX]

[DOI]

Math. Oper. Res., 2011

Hardness of Approximating Flow and Job Shop Scheduling Problems.

[BibT_eX]

[DOI]

J. ACM, 2011

Vertex Cover in Graphs with Locally Few Colors.

[BibT_eX]

[DOI]

Fabian Kuhn

Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

2010

Minimizing the sum of weighted completion times in a concurrent open shop.

[BibT_eX]

[DOI]

Oper. Res. Lett., 2010

On the use of different types of knowledge in metaheuristics based on constructing solutions.

[BibT_eX]

[DOI]

Christian Blum

Eng. Appl. Artif. Intell., 2010

2009

Improved Bounds for Flow Shop Scheduling.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 36th International Colloquium, 2009

2008

Hybridizations of Metaheuristics With Branch & Bound Derivates.

[BibT_eX]

[DOI]

Proceedings of the Hybrid Metaheuristics, An Emerging Approach to Optimization, 2008

Precedence Constraint Scheduling and Connections to Dimension Theory of Partial Orders.

[BibT_eX]

Bull. EATCS, 2008

(Acyclic) JobShops are Hard to Approximate.

[BibT_eX]

[DOI]

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

Approximating Single Machine Scheduling with Scenarios.

[BibT_eX]

[DOI]

Nikolaus Mutsanas

Proceedings of the Approximation, 2008

2007

The Robust Traveling Salesman Problem with Interval Data.

[BibT_eX]

[DOI]

Roberto Montemanni

János Barta

Transp. Sci., 2007

Scheduling with Precedence Constraints of Low Fractional Dimension.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatorial Optimization, 2007

Using Branch & Bound Concepts in Construction-Based Metaheuristics: Exploiting the Dual Problem Knowledge.

[BibT_eX]

[DOI]

Christian Blum

Proceedings of the Hybrid Metaheuristics, 4th International Workshop, 2007

Inapproximability Results for Sparsest Cut, Optimal Linear Arrangement, and Precedence Constrained Scheduling.

[BibT_eX]

[DOI]

Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, 2007

2006

Hybrid Metaheuristics for the Vehicle Routing Problem with Stochastic Demands.

[BibT_eX]

[DOI]

J. Math. Model. Algorithms, 2006

A linear time approximation scheme for the single machine scheduling problem with controllable processing times.

[BibT_eX]

[DOI]

J. Algorithms, 2006

Hybrid rounding techniques for knapsack problems.

[BibT_eX]

[DOI]

Marcus Hutter

Discret. Appl. Math., 2006

Single Machine Precedence Constrained Scheduling Is a Vertex Cover Problem.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2006

Approximating Precedence-Constrained Single Machine Scheduling by Coloring.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2006

2005

On-line scheduling to minimize max flow time: an optimal preemptive algorithm.

[BibT_eX]

[DOI]

Oper. Res. Lett., 2005

Maximum satisfiability: How good are tabu search and plateau moves in the worst-case?

[BibT_eX]

[DOI]

Eur. J. Oper. Res., 2005

Approximation schemes for job shop scheduling problems with controllable processing times.

[BibT_eX]

[DOI]

Roberto Solis-Oba

Eur. J. Oper. Res., 2005

2004

Scheduling To Minimize Max Flow Time: Off-Line And On-Line Algorithms.

[BibT_eX]

[DOI]

Int. J. Found. Comput. Sci., 2004

Approximation schemes for parallel machine scheduling problems with controllable processing times.

[BibT_eX]

[DOI]

Comput. Oper. Res., 2004

Applications Metaheuristics for the Vehicle Routing Problem with Stochastic Demands.

[BibT_eX]

[DOI]

Proceedings of the Parallel Problem Solving from Nature, 2004

MAX-2-SAT: How Good Is Tabu Search in the Worst-Case?

[BibT_eX]

[DOI]

Proceedings of the Nineteenth National Conference on Artificial Intelligence, 2004

2003

Efficient Approximation Schemes for Scheduling Problems with Release Dates and Delivery Times.

[BibT_eX]

[DOI]

J. Sched., 2003

Notes on Max Flow Time Minimization with Controllable Processing Times.

[BibT_eX]

[DOI]

Computing, 2003

Core Instances for Testing: A Case Study.

[BibT_eX]

[DOI]

Leonora Bianchi

Proceedings of the Experimental and Efficient Algorithms, Second International Workshop, 2003

On Minimizing Average Weighted Completion Time: A PTAS for the Job Shop Problem with Release Dates.

[BibT_eX]

[DOI]

Aleksei V. Fishkin

Proceedings of the Algorithms and Computation, 14th International Symposium, 2003

Scheduling to Minimize Max Flow Time: Offline and Online Algorithms.

[BibT_eX]

[DOI]

Proceedings of the Fundamentals of Computation Theory, 14th International Symposium, 2003

2002

Approximation schemes for scheduling problems.

[BibT_eX]

[DOI]

PhD thesis, 2002

A PTAS for the Single Machine Scheduling Problem with Controllable Processing Times.

[BibT_eX]

[DOI]

Proceedings of the Algorithm Theory, 2002

Metaheuristics for Group Shop Scheduling.

[BibT_eX]

[DOI]

Proceedings of the Parallel Problem Solving from Nature, 2002

A Comparison of the Performance of Different Metaheuristics on the Timetabling Problem.

[BibT_eX]

[DOI]

Proceedings of the Practice and Theory of Automated Timetabling IV, 2002

2001

An optimization methodology for intermodal terminal management.

[BibT_eX]

[DOI]

Andrea Emilio Rizzoli

Marco Zaffalon

J. Intell. Manuf., 2001

Job Shop Scheduling Problems with Controllable Processing Times.

[BibT_eX]

[DOI]

Roberto Solis-Oba

Proceedings of the Theoretical Computer Science, 7th Italian Conference, 2001

Grouping Techniques for One Machine Scheduling Subject to Precedence Constraints.

[BibT_eX]

[DOI]

Proceedings of the FST TCS 2001: Foundations of Software Technology and Theoretical Computer Science, 2001

Combining Arithmetic and Geometric Rounding Techniques for Knapsack Problems.

[BibT_eX]

[DOI]

Proceedings of the Fundamentals of Computation Theory, 13th International Symposium, 2001

Grouping Techniques for Scheduling Problems: Simpler and Faster.

[BibT_eX]

[DOI]

Aleksei V. Fishkin

Proceedings of the Algorithms, 2001

2000

Approximation Algorithms for Flexible Job Shop Problems.

[BibT_eX]

[DOI]

Roberto Solis-Oba

Proceedings of the LATIN 2000: Theoretical Informatics, 2000

Parallel Machine Scheduling Problems with Controllable Processing Times.

[BibT_eX]