Bin Packing via Discrepancy of Permutations

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

For any 𝜀 > 0, we prove that 𝑘-Dimensional Matching is hard to approximate within a factor of 𝑘/(12+𝜀) for large 𝑘 unless NP ⊆ BPP. Listed in Karp’s 21 NP-complete problems, 𝑘-Dimensional Matching is a benchmark computational complexity problem which we fi ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

Submodular functions are a widely studied topic in theoretical computer science. They have found several applications both theoretical and practical in the fields of economics, combinatorial optimization and machine learning. More recently, there have also ...

The concept of novelty is central to questions of creativity, innovation, and discovery. Despite the prominence in scientific inquiry and everyday discourse, there is a chronic ambiguity over its meaning and a surprising variety of empirical measures, whic ...

An instance of colorful k-center consists of points in a metric space that are colored red or blue, along with an integer k and a coverage requirement for each color. The goal is to find the smallest radius rho such that there exist balls of radius rho aro ...

Weighted flow time is a fundamental and very well-studied objective function in scheduling. In this paper, we study the setting of a single machine with preemptions. ...

Knapsack and Subset Sum are fundamental NP-hard problems in combinatorial optimization. Recently there has been a growing interest in understanding the best possible pseudopolynomial running times for these problems with respect to various parameters. In t ...

We consider the problem of solving integer programs of the form min {c^⊺ x : Ax = b, x ∈ ℤ_{⩾ 0}}, where A is a multistage stochastic matrix in the following sense: the primal treedepth of A is bounded by a parameter d, which means that the columns of A ca ...

An instance of colorful k-center consists of points in a metric space that are colored red or blue, along with an integer k and a coverage requirement for each color. The goal is to find the smallest radius ρ such that there exist balls of radius ρ around ...

Stochastic optimization is a popular modeling paradigm for decision-making under uncertainty and has a wide spectrum of applications in management science, economics and engineering. However, the stochastic optimization models one faces in practice are int ...

This thesis develops mathematical programming frameworks to operate electric autonomous vehicles in the context of ride-sharing services. The introduced problem is a novel variant of the Dial-a-Ride Problem (DARP), denoted by the electric Autonomous Dial-a ...

The distribution network restoration problem is by nature a mixed integer and non-linear optimization problem due to the switching decisions and Optimal Power Flow (OPF) constraints, respectively. The link between these two parts involves logical implicati ...

We introduce the analog of Kramers-Kronig dispersion relations for correlators of four scalar operators in an arbitrary conformal field theory. The correlator is expressed as an integral over its "absorptive part", defined as a double discontinuity, times ...

The next technological revolution will be interwoven to the proliferation of intelligent systems. As we bridge the gap between physical and cyber worlds, we will give rise to large-scale, multi-agent based technologies. A key challenge that cities of the f ...

We consider integer programming problems in standard form max{c(T)x : Ax = b, x >= 0, x is an element of Z(n)} where A is an element of Z(mxn), b is an element of Z(m), and c is an element of Z(n). We show that such an integer program can be solved in time ...

Bin Packing via Discrepancy of Permutations

Chat with Graph Search

Asymptotically Optimal Hardness for 𝑘-Set Packing and 𝑘-Matroid Intersection

Learning to Remove Cuts in Integer Linear Programming

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

Results on Sparse Integer Programming and Geometric Independent Sets

Approximation Algorithms for Allocation and Network Design

Data-Driven Control and Optimization under Noisy and Uncertain Conditions

Augmented Lagrangian Methods for Provable and Scalable Machine Learning

Streaming and Matching Problems with Submodular Functions

Nothing New Under the Sun: Novelty Constructs and Measures in Social Studies

Fair colorful k-center clustering

A (2+epsilon)-Approximation Algorithm for Preemptive Weighted Flow Time on a Single Machine

Knapsack and Subset Sum with Small Items

Efficient Sequential and Parallel Algorithms for Multistage Stochastic Integer Programming Using Proximity

Fair Colorful k-Center Clustering

Scalable Stochastic Optimization: Scenario Reduction with Guarantees

The electric autonomous dial-a-ride problem

A Novel Decomposition Solution Approach for the Restoration Problem in Distribution Networks

A conformal dispersion relation: correlations from absorption

Efficient Allocations in Constant Time: Towards Scalable Solutions in the Era of Large Scale Intelligent Systems

Proximity Results and Faster Algorithms for Integer Programming Using the Steinitz Lemma