The Experts below are selected from a list of 109698 Experts worldwide ranked by ideXlab platform
Mehran Mesbahi - One of the best experts on this subject based on the ideXlab platform.
-
A polynomial-time algorithm for solving certain classes of rank Minimization Problem
Proceedings of the 1999 American Control Conference (Cat. No. 99CH36251), 1999Co-Authors: L. Gurvits, Mehran MesbahiAbstract:We present a non-interior point based, polynomial-time algorithm for solving certain classes of rank Minimization Problem. Some of the structural properties of the rank Minimization Problem are also presented.
-
on the rank Minimization Problem and its control applications
Systems & Control Letters, 1998Co-Authors: Mehran MesbahiAbstract:We present several new results on the rank Minimization Problem over sets which are defined by linear matrix inequalities. We proceed to apply some of these results to propose a computational procedure for determining lower and upper bounds for the minimal-order dynamic output feedback which stabilizes a given linear time-invariant plant.
Lisa Zhang - One of the best experts on this subject based on the ideXlab platform.
-
Hardness of the Undirected Congestion Minimization Problem
SIAM Journal on Computing, 2007Co-Authors: Matthew Andrews, Lisa ZhangAbstract:We show that there is no $\gamma\log\log M/\log\log\log M$-approximation for the undirected congestion Minimization Problem unless $NP \subseteq ZPTIME(n^{{\rm polylog} n})$, where $M$ is the size of the graph and g is some positive constant.
-
logarithmic hardness of the directed congestion Minimization Problem
Symposium on the Theory of Computing, 2006Co-Authors: Matthew Andrews, Lisa ZhangAbstract:We show that for any constant e > 0, there is no Ω(log1-eM)-approximation algorithm for the directed congestion Minimization Problem on networks of size M unless NP ⊆ ZPTIME(npolylog n). This bound is almost tight given the O(log M/ log log M)-approximation via randomized rounding due to Raghavan and Thompson.
-
hardness of the undirected congestion Minimization Problem
Symposium on the Theory of Computing, 2005Co-Authors: Matthew Andrews, Lisa ZhangAbstract:We show that there is no (log log M)1-e approximation for the undirected congestion Minimization Problem unless NP ⊆ ZPTIME(npolylogn), where M is the size of the graph and e is any positive constant.
-
STOC - Hardness of the undirected congestion Minimization Problem
Proceedings of the thirty-seventh annual ACM symposium on Theory of computing - STOC '05, 2005Co-Authors: Matthew Andrews, Lisa ZhangAbstract:We show that there is no (log log M)1-e approximation for the undirected congestion Minimization Problem unless NP ⊆ ZPTIME(npolylogn), where M is the size of the graph and e is any positive constant.
Matthew Andrews - One of the best experts on this subject based on the ideXlab platform.
-
Hardness of the Undirected Congestion Minimization Problem
SIAM Journal on Computing, 2007Co-Authors: Matthew Andrews, Lisa ZhangAbstract:We show that there is no $\gamma\log\log M/\log\log\log M$-approximation for the undirected congestion Minimization Problem unless $NP \subseteq ZPTIME(n^{{\rm polylog} n})$, where $M$ is the size of the graph and g is some positive constant.
-
logarithmic hardness of the directed congestion Minimization Problem
Symposium on the Theory of Computing, 2006Co-Authors: Matthew Andrews, Lisa ZhangAbstract:We show that for any constant e > 0, there is no Ω(log1-eM)-approximation algorithm for the directed congestion Minimization Problem on networks of size M unless NP ⊆ ZPTIME(npolylog n). This bound is almost tight given the O(log M/ log log M)-approximation via randomized rounding due to Raghavan and Thompson.
-
hardness of the undirected congestion Minimization Problem
Symposium on the Theory of Computing, 2005Co-Authors: Matthew Andrews, Lisa ZhangAbstract:We show that there is no (log log M)1-e approximation for the undirected congestion Minimization Problem unless NP ⊆ ZPTIME(npolylogn), where M is the size of the graph and e is any positive constant.
-
STOC - Hardness of the undirected congestion Minimization Problem
Proceedings of the thirty-seventh annual ACM symposium on Theory of computing - STOC '05, 2005Co-Authors: Matthew Andrews, Lisa ZhangAbstract:We show that there is no (log log M)1-e approximation for the undirected congestion Minimization Problem unless NP ⊆ ZPTIME(npolylogn), where M is the size of the graph and e is any positive constant.
Michael A Trick - One of the best experts on this subject based on the ideXlab platform.
-
the timetable constrained distance Minimization Problem
Annals of Operations Research, 2009Co-Authors: Rasmus V Rasmussen, Michael A TrickAbstract:We define the timetable constrained distance Minimization Problem (TCDMP) which is a sports scheduling Problem applicable for tournaments where the total travel distance must be minimized. The Problem consists of finding an optimal home-away assignment when the opponents of each team in each time slot are given. We present an integer programming, a constraint programming formulation and describe two alternative solution methods: a hybrid integer programming/constraint programming approach and a branch and price algorithm. We test all four solution methods on benchmark Problems and compare the performance. Furthermore, we present a new heuristic solution method called the circular traveling salesman approach (CTSA) for solving the traveling tournament Problem. The solution method is able to obtain high quality solutions almost instantaneously, and by applying the TCDMP, we show how the solutions can be further improved.
-
the timetable constrained distance Minimization Problem
Integration of AI and OR Techniques in Constraint Programming, 2006Co-Authors: Rasmus V Rasmussen, Michael A TrickAbstract:The Timetable Constrained Distance Minimization Problem is a sports scheduling Problem applicable for tournaments where the total travel distance must be minimized. In this paper we define the Problem and present an integer programming and a constraint programming formulation for the Problem. Furthermore, we describe a hybrid integer programming/constraint programming approach and a branch and bound algorithm for solving the Timetable Constrained Distance Minimization Problem. Finally, the computational performances of the four solution methods are tested and compared.
-
CPAIOR - The timetable constrained distance Minimization Problem
Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, 2006Co-Authors: Rasmus V Rasmussen, Michael A TrickAbstract:The Timetable Constrained Distance Minimization Problem is a sports scheduling Problem applicable for tournaments where the total travel distance must be minimized. In this paper we define the Problem and present an integer programming and a constraint programming formulation for the Problem. Furthermore, we describe a hybrid integer programming/constraint programming approach and a branch and bound algorithm for solving the Timetable Constrained Distance Minimization Problem. Finally, the computational performances of the four solution methods are tested and compared.
Abraham Duarte - One of the best experts on this subject based on the ideXlab platform.
-
scatter search for the profile Minimization Problem
Networks, 2015Co-Authors: Jesus Sanchezoro, Abraham Duarte, Manuel Laguna, Rafael MartiAbstract:We study the Problem of minimizing the profile of a graph and develop a solution method by following the tenets of scatter search. Our procedure exploits the network structure of the Problem and includes strategies that produce a computationally efficient and agile search. Among several mechanisms, our search includes path relinking as the basis for combining solutions to generate new ones. The profile Minimization Problem PMP is NP-Hard and has relevant applications in numerical analysis techniques that rely on manipulating large sparse matrices. The Problem was proposed in the early 1970s but the state-of-the-art does not include a method that could be considered powerful by today's computing standards. Extensive computational experiments show that we have accomplished our goal of pushing the envelope and establishing a new standard in the solution of the PMP. © 2014 Wiley Periodicals, Inc. NETWORKS, Vol. 651, 10-21. 2015
-
variable formulation search for the cutwidth Minimization Problem
Applied Soft Computing, 2013Co-Authors: Eduardo G Pardo, Juan Jose Pantrigo, Nenad Mladenovic, Abraham DuarteAbstract:Many optimization Problems are formulated as min-max Problems where the objective function consist of minimizing a maximum value. In this case, it is usual that many solutions of the Problem has associated the same value of the objective function. When this happens it is difficult to determine which solution is more promising to continue the search. In this paper we propose a new variant of the Variable Neighbourhood Search methodology to tackle this kind of Problems. The new variant, named Variable Formulation Search, makes use of alternative formulations of the Problem to determine which solution is more promising when they have the same value of the objective function in the original formulation. We do that in shaking, local search and neighbourhood change steps of the basic Variable Neighbourhood Search. We apply the new methodology to the Cutwidth Minimization Problem. Computational results show that our proposal outperforms previous algorithms in the state of the art in terms of quality and computing time.
-
branch and bound for the cutwidth Minimization Problem
Computers & Operations Research, 2013Co-Authors: Rafael Marti, Juan Jose Pantrigo, Abraham Duarte, Eduardo G PardoAbstract:The cutwidth Minimization Problem consists of finding a linear arrangement of the vertices of a graph where the maximum number of cuts between the edges of the graph and a line separating consecutive vertices is minimized. We first review previous approaches for special classes of graphs, followed by lower bounds and then a linear integer formulation for the general Problem. We then propose a branch-and-bound algorithm based on different lower bounds on the cutwidth of partial solutions. Additionally, we introduce a Greedy Randomized Adaptive Search Procedure (GRASP) heuristic to obtain good initial solutions. The combination of the branch-and-bound and GRASP methods results in optimal solutions or a reduced relative gap (difference between upper and lower bounds) on the instances tested. Empirical results with a collection of previously reported instances indicate that the proposed algorithm is able to solve all the small instances (up to 32 vertices) as well as some of the large instances tested (up to 158 vertices) using less than 30 minutes of CPU time. We compare the results of our method with previous lower bounds, and with the best previous linear integer formulation solved using Cplex. Both comparisons favor the proposed procedure.
-
scatter search for the cutwidth Minimization Problem
Annals of Operations Research, 2012Co-Authors: Juan Jose Pantrigo, Rafael Marti, Abraham Duarte, Eduardo G PardoAbstract:The cutwidth Minimization Problem consists of finding a linear layout of a graph so that the maximum linear cut of edges is minimized. This NP-hard Problem has applications in network scheduling, automatic graph drawing and information retrieval. We propose a heuristic method based on the Scatter Search (SS) methodology for finding approximate solutions to this optimization Problem. This metaheuristic explores solution space by evolving a set of reference points. Our SS method is based on a GRASP constructive algorithm, a local search strategy based on insertion moves and voting-based combination methods. We also introduce a new measure to control the diversity in the search process. Empirical results with 252 previously reported instances indicate that the proposed procedure compares favorably to previous metaheuristics for this Problem, such as Simulated Annealing and Evolutionary Path Relinking.