A5053978143- Optimization and Search Problems
- Scheduling and Optimization Algorithms
- Complexity and Algorithms in Graphs
- Optimization and Packing Problems
- Advanced Graph Theory Research
- Advanced Optimization Algorithms Research
- Advanced Manufacturing and Logistics Optimization
- Constraint Satisfaction and Optimization
- Vehicle Routing Optimization Methods
- Formal Methods in Verification
- Commutative Algebra and Its Applications
- Polynomial and algebraic computation
- VLSI and FPGA Design Techniques
- Metaheuristic Optimization Algorithms Research
- Auction Theory and Applications
- Game Theory and Voting Systems
- Distributed and Parallel Computing Systems
- Transportation Planning and Optimization
- Numerical Methods and Algorithms
- Machine Learning and Algorithms
- Transportation and Mobility Innovations
- Computational Geometry and Mesh Generation
- Maritime Ports and Logistics
- Sparse and Compressive Sensing Techniques
- Advanced Multi-Objective Optimization Algorithms
Dalle Molle Institute for Artificial Intelligence Research
2014-2025
University of Applied Sciences and Arts of Southern Switzerland
2004-2025
Universitat Politècnica de Catalunya
2008
The traveling salesman problem is one of the most famous combinatorial optimization problems and has been intensively studied. Many extensions to basic have also proposed, with aim making resulting mathematical models as realistic possible. We present a new extension problem, where travel times are specified range possible values. This model reflects intrinsic difficulties estimating in reality. apply robust deviation criterion drive over interval data so obtained. Some interesting...
We consider the Minimum Linear Arrangement problem and (Uniform) Sparsest Cut problem. So far, these two notorious NP-hard graph problems have resisted all attempts to prove inapproximability results. show that they no polynomial time approximation scheme, unless NP-complete can be solved in randomized subexponential time. Furthermore, we same techniques used for Maximum Edge Biclique problem, which obtain a hardness factor similar previous results but under more standard assumption.
In recent years, copositive programming has received significant attention for its ability to model hard problems in both discrete and continuous optimization. Several relaxations of programs based on semidefinite (SDP) have been proposed the literature, meant provide tractable bounds. However, while these SDP-based are amenable ellipsoid algorithm interior point methods, it is not immediately obvious that they can be solved polynomial time (even approximately). this paper, we consider...
We consider the single-machine scheduling problem to minimize weighted sum of completion times under precedence constraints. In a series recent papers, it was established that this is special case minimum vertex cover. paper, we show cover graph associated with exactly incomparable pairs defined in dimension theory partial orders. Exploiting relationship allows us present framework for obtaining (2-2/f)-approximation algorithms, provided set constraints has fractional at most f. Our approach...
We are given a set of clients with budget constraints and indivisible items. Each client is willing to buy one or more bundles (at most) k items each (bundles can be seen as hyperedges in k-hypergraph). If i gets bundle e, she pays bi,e yields net profit wi,e. The Hypermatching Assignment Problem (HAP) assign pairwise disjoint so maximize the total while respecting budgets. This problem has various applications production planning budget-constrained auctions generalizes well-studied problems...
Previous chapter Next Full AccessProceedings Proceedings of the 2013 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)How to Sell Hyperedges: The Hypermatching Assignment ProblemMarek Cygan, Fabrizio Grandoni, and Monaldo MastrolilliMarek Mastrolillipp.342 - 351Chapter DOI:https://doi.org/10.1137/1.9781611973105.25PDFBibTexSections ToolsAdd favoritesExport CitationTrack CitationsEmail SectionsAboutAbstract We are given a set clients with budget constraints indivisible items. Each...
For binary polynomial optimization problems of degree 2d with n variables Sakaue, Takeda, Kim, and Ito [ 33 ] proved that the \(\lceil \frac{n+2d-1}{2}\rceil\) th semidefinite (SDP) relaxation in SoS/Lasserre hierarchy SDP relaxations provides exact optimal value. When is an odd number, we show their analysis tight, i.e., prove \(\frac{n+2d-1}{2}\) levels are also necessary. Laurent 24 showed Sherali-Adams requires to detect empty integer hull a linear representation set no integral points....
We consider several variants of the job shop problem that is a fundamental and classical in scheduling. The currently best approximation algorithms have worse than logarithmic performance guarantee, but only previously known inapproximability result says it NP-hard to approximate shops within factor less 5/4. Closing this big approximability gap well-known long-standing open problem. This article closes many gaps our understanding hardness answers questions literature. It shown first...