Roberto Solis-Oba
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Roberto Solis-Oba has a total of 17 co-authors. Here are the top co-authors by number of shared publications:
Nasim Samei
Computer Science, University of Western Ontario, London, ON, Canada
5 shared publications- Andrew Bloch-Hansen
Western University
4 shared publications - Daniel R. Page
PageWizard Games, Learning & Entertainment
2 shared publications - Andy Yu
Department of Computer Science, Western University, London, Canada
1 shared publication - Bahlul Haider
Department of Computer Science, University of Western Ontario, N6A 5B7 London, Ontario, Canada
1 shared publication - Björn Schumacher
Kiel University, Kiel, Germany
1 shared publication
Latest Publications
- Open Access
- 1 October 2025
- Published by Universitatsbibliothek Kiel
Faster EPTAS for Scheduling on Uniform Machines
We present an efficient polynomial-time approximation scheme (EPTAS) for the problem of scheduling jobs on parallel uniform machines that improves all previously known EPTAS for the problem. Our algorithm uses a Mixed Integer Linear Program (MILP) formulation for a relaxed version of the problem. We simplify the MILP by repeatedly removing carefully selected sets of jobs and machines until all integer variables have been removed. Then, we build up the solution through the use of a dynamic programming approach, enumeration, and linear program solving. Notable about our approach is that our algorithm only uses an LP solver, different from previous EPTAS approaches where MILP solvers are necessary.
- 1 October 2025
- Published by Universitatsbibliothek Kiel
Open AccessFaster EPTAS for Scheduling on Uniform Machines
We present an efficient polynomial-time approximation scheme (EPTAS) for the problem of scheduling jobs on parallel uniform machines that improves all previously known EPTAS for the problem. Our algorithm uses a Mixed Integer Linear Program (MILP) formulation for a relaxed version of the problem. We simplify the MILP by repeatedly removing carefully selected sets of jobs and machines until all integer variables have been removed. Then, we build up the solution through the use of a dynamic programming approach, enumeration, and linear program solving. Notable about our approach is that our algorithm only uses an LP solver, different from previous EPTAS approaches where MILP solvers are necessary.
- 1 April 2025
- Published by Springer Nature in Theory of Computing Systems
- Vol. 69 (2) , 1-37
High Multiplicity Strip Packing with Three Rectangle Types
- 1 April 2025
- Published by Springer Nature in Theory of Computing Systems
- Vol. 69 (2) , 1-37
High Multiplicity Strip Packing with Three Rectangle Types
- 25 March 2025
- Published by Springer Nature in Acta Informatica
- Vol. 62 (2) , 1-29
The thief orienteering problem on 2-terminal series–parallel graphs
- 25 March 2025
- Published by Springer Nature in Acta Informatica
- Vol. 62 (2) , 1-29
The thief orienteering problem on 2-terminal series–parallel graphs
- 22 May 2024
- Published by Springer Nature
- p. 248-262
The Thief Orienteering Problem on Series-Parallel Graphs
- 22 May 2024
- Published by Springer Nature
- p. 248-262
The Thief Orienteering Problem on Series-Parallel Graphs
- 3 June 2023
- Published by Springer Nature
- p. 87-98
A Polynomial-Time Approximation Scheme for Thief Orienteering on Directed Acyclic Graphs
- 3 June 2023
- Published by Springer Nature
- p. 87-98
A Polynomial-Time Approximation Scheme for Thief Orienteering on Directed Acyclic Graphs
- 26 October 2019
- Published by Springer Nature in Theory of Computing Systems
- Vol. 63 (8) , 1755-1756
Guest Editorial: Special Issue on Approximation and Online Algorithms
- 26 October 2019
- Published by Springer Nature in Theory of Computing Systems
- Vol. 63 (8) , 1755-1756
Guest Editorial: Special Issue on Approximation and Online Algorithms
- Open Access
- 18 December 2018
- Published by PeerJ
A local search algorithm for the constrained max cut problem on hypergraphs.
In the constrained max k-cut problem on hypergraphs, we are given a weighted hypergraph H=(V, E), an integer k and a set c of constraints. The goal is to divide the set V of vertices into k disjoint partitions in such a way that the sum of the weights of the hyperedges having at least two endpoints in different partitions is maximized and the partitions satisfy all the constraints in c. In this paper we present a local search algorithm for the constrained max k-cut problem on hypergraphs and show that it has approximation ratio 1-1/k for a variety of constraints c, such as for the constraints defining the max Steiner k-cut problem, the max multiway cut problem and the max k-cut problem. We also show that our local search algorithm can be used on the max k-cut problem with given sizes of parts and on the capacitated max k-cut problem, and has approximation ratio 1-|Vmax|/|V|, where |Vmax| is the cardinality of the biggest partition. In addition, we present a local search algorithm for the directed max k-cut problem that has approximation ratio (k-1)/(3k-2).
- 18 December 2018
- Published by PeerJ
Open AccessA local search algorithm for the constrained max cut problem on hypergraphs.
In the constrained max k-cut problem on hypergraphs, we are given a weighted hypergraph H=(V, E), an integer k and a set c of constraints. The goal is to divide the set V of vertices into k disjoint partitions in such a way that the sum of the weights of the hyperedges having at least two endpoints in different partitions is maximized and the partitions satisfy all the constraints in c. In this paper we present a local search algorithm for the constrained max k-cut problem on hypergraphs and show that it has approximation ratio 1-1/k for a variety of constraints c, such as for the constraints defining the max Steiner k-cut problem, the max multiway cut problem and the max k-cut problem. We also show that our local search algorithm can be used on the max k-cut problem with given sizes of parts and on the capacitated max k-cut problem, and has approximation ratio 1-|Vmax|/|V|, where |Vmax| is the cardinality of the biggest partition. In addition, we present a local search algorithm for the directed max k-cut problem that has approximation ratio (k-1)/(3k-2).
- Open Access
- 18 December 2018
- Published by PeerJ
A local search algorithm for the constrained max cut problem on hypergraphs.
In the constrained max k-cut problem on hypergraphs, we are given a weighted hypergraph H=(V, E), an integer k and a set c of constraints. The goal is to divide the set V of vertices into k disjoint partitions in such a way that the sum of the weights of the hyperedges having at least two endpoints in different partitions is maximized and the partitions satisfy all the constraints in c. In this paper we present a local search algorithm for the constrained max k-cut problem on hypergraphs and show that it has approximation ratio 1-1/k for a variety of constraints c, such as for the constraints defining the max Steiner k-cut problem, the max multiway cut problem and the max k-cut problem. We also show that our local search algorithm can be used on the max k-cut problem with given sizes of parts and on the capacitated max k-cut problem, and has approximation ratio 1-|Vmax|/|V|, where |Vmax| is the cardinality of the biggest partition. In addition, we present a local search algorithm for the directed max k-cut problem that has approximation ratio (k-1)/(3k-2).
- 18 December 2018
- Published by PeerJ
Open AccessA local search algorithm for the constrained max cut problem on hypergraphs.
In the constrained max k-cut problem on hypergraphs, we are given a weighted hypergraph H=(V, E), an integer k and a set c of constraints. The goal is to divide the set V of vertices into k disjoint partitions in such a way that the sum of the weights of the hyperedges having at least two endpoints in different partitions is maximized and the partitions satisfy all the constraints in c. In this paper we present a local search algorithm for the constrained max k-cut problem on hypergraphs and show that it has approximation ratio 1-1/k for a variety of constraints c, such as for the constraints defining the max Steiner k-cut problem, the max multiway cut problem and the max k-cut problem. We also show that our local search algorithm can be used on the max k-cut problem with given sizes of parts and on the capacitated max k-cut problem, and has approximation ratio 1-|Vmax|/|V|, where |Vmax| is the cardinality of the biggest partition. In addition, we present a local search algorithm for the directed max k-cut problem that has approximation ratio (k-1)/(3k-2).
- Open Access
- 18 December 2018
- Published by PeerJ in PeerJ Preprints
A local search algorithm for the constrained max cut problem on hypergraphs.
In the constrained max k-cut problem on hypergraphs, we are given a weighted hypergraph H=(V, E), an integer k and a set c of constraints. The goal is to divide the set V of vertices into k disjoint partitions in such a way that the sum of the weights of the hyperedges having at least two endpoints in different partitions is maximized and the partitions satisfy all the constraints in c. In this paper we present a local search algorithm for the constrained max k-cut problem on hypergraphs and show that it has approximation ratio 1-1/k for a variety of constraints c, such as for the constraints defining the max Steiner k-cut problem, the max multiway cut problem and the max k-cut problem. We also show that our local search algorithm can be used on the max k-cut problem with given sizes of parts and on the capacitated max k-cut problem, and has approximation ratio 1-|Vmax|/|V|, where |Vmax| is the cardinality of the biggest partition. In addition, we present a local search algorithm for the directed max k-cut problem that has approximation ratio (k-1)/(3k-2).
- 18 December 2018
- Published by PeerJ in PeerJ Preprints
Open AccessA local search algorithm for the constrained max cut problem on hypergraphs.
In the constrained max k-cut problem on hypergraphs, we are given a weighted hypergraph H=(V, E), an integer k and a set c of constraints. The goal is to divide the set V of vertices into k disjoint partitions in such a way that the sum of the weights of the hyperedges having at least two endpoints in different partitions is maximized and the partitions satisfy all the constraints in c. In this paper we present a local search algorithm for the constrained max k-cut problem on hypergraphs and show that it has approximation ratio 1-1/k for a variety of constraints c, such as for the constraints defining the max Steiner k-cut problem, the max multiway cut problem and the max k-cut problem. We also show that our local search algorithm can be used on the max k-cut problem with given sizes of parts and on the capacitated max k-cut problem, and has approximation ratio 1-|Vmax|/|V|, where |Vmax| is the cardinality of the biggest partition. In addition, we present a local search algorithm for the directed max k-cut problem that has approximation ratio (k-1)/(3k-2).
- Open Access
- 18 December 2018
- Published by PeerJ in PeerJ Preprints
A local search algorithm for the constrained max cut problem on hypergraphs.
In the constrained max k-cut problem on hypergraphs, we are given a weighted hypergraph H=(V, E), an integer k and a set c of constraints. The goal is to divide the set V of vertices into k disjoint partitions in such a way that the sum of the weights of the hyperedges having at least two endpoints in different partitions is maximized and the partitions satisfy all the constraints in c. In this paper we present a local search algorithm for the constrained max k-cut problem on hypergraphs and show that it has approximation ratio 1-1/k for a variety of constraints c, such as for the constraints defining the max Steiner k-cut problem, the max multiway cut problem and the max k-cut problem. We also show that our local search algorithm can be used on the max k-cut problem with given sizes of parts and on the capacitated max k-cut problem, and has approximation ratio 1-|Vmax|/|V|, where |Vmax| is the cardinality of the biggest partition. In addition, we present a local search algorithm for the directed max k-cut problem that has approximation ratio (k-1)/(3k-2).
- 18 December 2018
- Published by PeerJ in PeerJ Preprints
Open AccessA local search algorithm for the constrained max cut problem on hypergraphs.
In the constrained max k-cut problem on hypergraphs, we are given a weighted hypergraph H=(V, E), an integer k and a set c of constraints. The goal is to divide the set V of vertices into k disjoint partitions in such a way that the sum of the weights of the hyperedges having at least two endpoints in different partitions is maximized and the partitions satisfy all the constraints in c. In this paper we present a local search algorithm for the constrained max k-cut problem on hypergraphs and show that it has approximation ratio 1-1/k for a variety of constraints c, such as for the constraints defining the max Steiner k-cut problem, the max multiway cut problem and the max k-cut problem. We also show that our local search algorithm can be used on the max k-cut problem with given sizes of parts and on the capacitated max k-cut problem, and has approximation ratio 1-|Vmax|/|V|, where |Vmax| is the cardinality of the biggest partition. In addition, we present a local search algorithm for the directed max k-cut problem that has approximation ratio (k-1)/(3k-2).