Abstract In this work, we work on robust models, i.e. ones that incorporate uncertainty in the feasible set. The aim is to find a minimum-cost subgraph satisfying the connectivity requirement. Most existing models of robust network design assume uniform scenario sets. Our algorithm combines combinatorial and LP-based techniques. We are convinced our methods are suitable for solving other robust problems in... In this work, we work on robust models, i.e. ones that incorporate uncertainty in the feasible set. The aim is to find a minimum-cost subgraph satisfying the connectivity requirement. Most existing models of robust network design assume uniform scenario sets. Our algorithm combines combinatorial and LP-based techniques. We are convinced our methods are suitable for solving other robust problems in planar graphs. Read More Read Less

Abstract This paper generalizes Cutler and Shiloah’s algorithm for routing with well-separated destinations. We provide an O(n1/4· log n) approximation algorithm for NDP on grids and give the APX-hardness proof. In this work, we discuss the integrality gap of the multicommodity flow LP relaxation when all terminals are far from the grid boundary.... This paper generalizes Cutler and Shiloah’s algorithm for routing with well-separated destinations. We provide an O(n1/4· log n) approximation algorithm for NDP on grids and give the APX-hardness proof. In this work, we discuss the integrality gap of the multicommodity flow LP relaxation when all terminals are far from the grid boundary. Read More Read Less

Abstract Maximum constraint satisfaction problem (Max CSP) is a problem of great interest in approximation algorithms since it encapsulates many natural optimization problems. The goal is to find an assignment to all the variables that satisfy as many constraints as possible. In this work, our primary focus is the case where each constraint depends on exactly k = 2 variables and... Maximum constraint satisfaction problem (Max CSP) is a problem of great interest in approximation algorithms since it encapsulates many natural optimization problems. The goal is to find an assignment to all the variables that satisfy as many constraints as possible. In this work, our primary focus is the case where each constraint depends on exactly k = 2 variables and the large alphabet size. This case has been intensively researched regarding the hardness of approximation and multi-prover games. Read More Read Less