Publications related to Maximizing Symmetric Submodular Functions

Related publications (31)

Integer points in the degree-sequence polytope

An integer vector 𝑏 ∈ Z𝑑 is a degree sequence if there exists a hypergraph with vertices {1, … , 𝑑} such that each 𝑏𝑖 is the number of hyperedges containing 𝑖. The degree-sequence polytope 𝒵 𝑑 is the convex hull of all degree sequences. We show that all bu ...

ELSEVIER2025

A ride time-oriented scheduling algorithm for dial-a-ride problems

Nikolaos Geroliminis, Claudia Bongiovanni, Mor Kaspi

This paper offers a new algorithm to efficiently optimize scheduling decisions for dial-a-ride problems (DARPs), including problem variants considering electric and autonomous vehicles (e-ADARPs). The scheduling heuristic, based on linear programming theor ...

Pergamon-Elsevier Science Ltd2024

Quantifying the Unknown: Data-Driven Approaches and Applications in Energy Systems

Paul Scharnhorst

In light of the challenges posed by climate change and the goals of the Paris Agreement, electricity generation is shifting to a more renewable and decentralized pattern, while the operation of systems like buildings is increasingly electrified. This calls ...

EPFL2024

Learning to Remove Cuts in Integer Linear Programming

Volkan Cevher, Grigorios Chrysos, Efstratios Panteleimon Skoulakis

Cutting plane methods are a fundamental approach for solving integer linear programs (ILPs). In each iteration of such methods, additional linear constraints (cuts) are introduced to the constraint set with the aim of excluding the previous fractional opti ...

2024

BENIGN LANDSCAPES OF LOW-DIMENSIONAL RELAXATIONS FOR ORTHOGONAL SYNCHRONIZATION ON GENERAL GRAPHS

Nicolas Boumal

Orthogonal group synchronization is the problem of estimating n elements Z(1),& mldr;,Z(n) from the rxr orthogonal group given some relative measurements R-ij approximate to Z(i)Z(j)(-1). The least-squares formulation is nonconvex. To avoid its local minim ...

Siam Publications2024

Perturbed Utility Stochastic Traffic Assignment

Rui Yao

This paper develops a fast algorithm for computing the equilibrium assignment with the perturbed utility route choice (PURC) model. Without compromise, this allows the significant advantages of the PURC model to be used in large-scale applications. We form ...

Informs2024

Optimization Algorithms for Decentralized, Distributed and Collaborative Machine Learning

Anastasiia Koloskova

Distributed learning is the key for enabling training of modern large-scale machine learning models, through parallelising the learning process. Collaborative learning is essential for learning from privacy-sensitive data that is distributed across various ...

EPFL2024

The effect of smooth parametrizations on nonconvex optimization landscapes

Nicolas Boumal

We develop new tools to study landscapes in nonconvex optimization. Given one optimization problem, we pair it with another by smoothly parametrizing the domain. This is either for practical purposes (e.g., to use smooth optimization algorithms with good g ...

Springer Heidelberg2024

Reach For the Arcs: Reconstructing Surfaces from SDFs via Tangent Points

Yingying Ren

We introduce an algorithm to reconstruct a mesh from discrete samples of a shape's Signed Distance Function (SDF). A simple geometric reinterpretation of the SDF lets us formulate the problem through a point cloud, from which a surface can be extracted wit ...

Association for Computing Machinery2024

Exact Obstacle Avoidance for Robots in Complex and Dynamic Environments Using Local Modulation

Lukas Huber

Robots outside of the fenced factories have to deal with continuously changing environment, this requires fast and flexible modes of control. Planning methods or complex learning models can find optimal paths in complex surroundings, but they are computati ...

EPFL2024

A Combination Technique for Optimal Control Problems Constrained by Random PDEs

Fabio Nobile, Tommaso Vanzan

We present a combination technique based on mixed differences of both spatial approximations and quadrature formulae for the stochastic variables to solve efficiently a class of optimal control problems (OCPs) constrained by random partial differential equ ...

2024

Scalable constrained optimization

Maria-Luiza Vladarean

Modern optimization is tasked with handling applications of increasingly large scale, chiefly due to the massive amounts of widely available data and the ever-growing reach of Machine Learning. Consequently, this area of research is under steady pressure t ...

EPFL2024

Approximation Algorithms for Allocation and Network Design

Etienne Michel François Bamas

In this thesis, we give new approximation algorithms for some NP-hard problems arising in resource allocation and network design. As a resource allocation problem, we study the Santa Claus problem (also known as the MaxMin Fair Allocation problem) in which ...

EPFL2023

Results on Sparse Integer Programming and Geometric Independent Sets

Jana Tabea Cslovjecsek

An integer linear program is a problem of the form max{c^T x : Ax=b, x >= 0, x integer}, where A is in Z^(n x m), b in Z^m, and c in Z^n. Solving an integer linear program is NP-hard in general, but there are several assumptions for which it becomes fixed ...

EPFL2023

Augmented Lagrangian Methods for Provable and Scalable Machine Learning

Mehmet Fatih Sahin

Non-convex constrained optimization problems have become a powerful framework for modeling a wide range of machine learning problems, with applications in k-means clustering, large- scale semidefinite programs (SDPs), and various other tasks. As the perfor ...

EPFL2023

A Spatial Branch and Bound Algorithm for Continuous Pricing with Advanced Discrete Choice Demand Modeling

Michel Bierlaire

In this paper, we present a spatial branch and bound algorithm to tackle the continuous pricing problem, where demand is captured by an advanced discrete choice model (DCM). Advanced DCMs, like mixed logit or latent class models, are capable of modeling de ...

2023

Data-Driven Control and Optimization under Noisy and Uncertain Conditions

Baiwei Guo

Control systems operating in real-world environments often face disturbances arising from measurement noise and model mismatch. These factors can significantly impact the perfor- mance and safety of the system. In this thesis, we aim to leverage data to de ...

EPFL2023

Multi-robot task allocation for safe planning against stochastic hazard dynamics

Maryam Kamgarpour

We address multi-robot safe mission planning in uncertain dynamic environments. This problem arises in several applications including safety-critical exploration, surveillance, and emergency rescue missions. Computation of a multi-robot optimal control pol ...

IEEE2023

Primal-Dual Contextual Bayesian Optimization for Control System Online Optimization with Time-Average Constraints

Colin Neil Jones, Yuning Jiang, Wenjie Xu

This paper studies the problem of online performance optimization of constrained closed-loop control systems, where both the objective and the constraints are unknown black-box functions affected by exogenous time-varying contextual disturbances. A primal- ...

IEEE2023

Structural impact of the start-up sequence on Pelton turbines lifetime: Analytical prediction and polynomial optimization

Mario Paolone, Elena Vagnoni, Aldo Leonardo Alerci

Hydropower plants play a crucial role in the power system facing ambitious renewable energy targets. Due to their inherent controllability, they are well suited to provide flexibility to the grid. However, an increased flexibility provision leads to a prol ...

Pergamon-Elsevier Science Ltd2023