Bruno Escoffier

Dimitris Fotakis

Panagiotis Patsilinakos

CoRR, February, 2025

Approximation results on resource leveling problems.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2025

Temporal Connectivity Augmentation.

[BibT_eX]

[DOI]

Thomas Bellitto

Jules Bouton Popper

Proceedings of the 4th Symposium on Algorithmic Foundations of Dynamic Networks, 2025

Estimating the Electoral Consequences of Legislative Redistricting in France.

[BibT_eX]

[DOI]

Proceedings of the 2025 ACM Conference on Fairness, Accountability, and Transparency, 2025

2024

Resource leveling: complexity of a unit execution time two-processor scheduling variant and related problems.

[BibT_eX]

[DOI]

J. Sched., December, 2024

Euclidean preferences in the plane under $\varvec{\ell _1},$$\varvec{\ell _2}$ and $\varvec{\ell _\infty }$ norms.

[BibT_eX]

[DOI]

Soc. Choice Welf., August, 2024

Anchored rescheduling problem with non-availability periods.

[BibT_eX]

[DOI]

Oper. Res. Lett., 2024

Anchor-robust project scheduling with non-availability periods.

[BibT_eX]

[DOI]

Discret. Optim., 2024

Canadian Traveller Problems in Temporal Graphs.

[BibT_eX]

[DOI]

CoRR, 2024

Improved FPT Approximation for Non-metric TSP.

[BibT_eX]

[DOI]

CoRR, 2024

Resource Leveling: Complexity of a UET two-processor scheduling variant and related problems.

[BibT_eX]

[DOI]

CoRR, 2024

Parsimonious Learning-Augmented Approximations for Dense Instances of NP-hard Problems.

[BibT_eX]

[DOI]

Proceedings of the Forty-first International Conference on Machine Learning, 2024

2023

Target-based computer-assisted orchestration: Complexity and approximation algorithms.

[BibT_eX]

[DOI]

Carmine-Emanuele Cella

Mila Rocco

Alexandre Teiller

Eur. J. Oper. Res., 2023

Online TSP with Known Locations.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Data Structures - 18th International Symposium, 2023

Restless Exploration of Periodic Temporal Graphs.

[BibT_eX]

[DOI]

Thomas Bellitto

Cyril Conchon-Kerjan

Proceedings of the 2nd Symposium on Algorithmic Foundations of Dynamic Networks, 2023

Learning-Augmented Online TSP on Rings, Trees, Flowers and (Almost) Everywhere Else.

[BibT_eX]

[DOI]

Proceedings of the 31st Annual European Symposium on Algorithms, 2023

Algorithmic Recognition of 2-Euclidean Preferences.

[BibT_eX]

[DOI]

Proceedings of the ECAI 2023 - 26th European Conference on Artificial Intelligence, September 30 - October 4, 2023, Kraków, Poland, 2023

Online 2-stage Stable Matching.

[BibT_eX]

[DOI]

Paul Youssef

Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems, 2023

2022

In memory of Jérôme Monnot.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2022

Online learning for min-max discrete problems.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2022

A simple rounding scheme for multistage optimization.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2022

Weighted majority tournaments and Kemeny ranking with 2-dimensional Euclidean preferences.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2022

Canadian Traveller Problem with Predictions.

[BibT_eX]

[DOI]

Proceedings of the Approximation and Online Algorithms - 20th International Workshop, 2022

2021

Kemeny ranking is NP-hard for 2-dimensional Euclidean preferences.

[BibT_eX]

[DOI]

CoRR, 2021

Measuring Nearly Single-Peakedness of an Electorate: Some New Insights.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Decision Theory - 7th International Conference, 2021

2020

LP-Based Algorithms for Multistage Minimization Problems.

[BibT_eX]

[DOI]

Alexander V. Kononov

Proceedings of the Approximation and Online Algorithms - 18th International Workshop, 2020

Recognizing Single-Peaked Preferences on an Arbitrary Graph: Complexity and Algorithms.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Game Theory - 13th International Symposium, 2020

Social Ranking Manipulability for the CP-Majority, Banzhaf and Lexicographic Excellence Solutions.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, 2020

Iterative Delegations in Liquid Democracy with Restricted Preferences.

[BibT_eX]

[DOI]

Hugo Gilbert

Adèle Pass-Lanneau

Proceedings of the Thirty-Fourth AAAI Conference on Artificial Intelligence, 2020

2019

The Convergence of Iterative Delegations in Liquid Democracy in a Social Network.

[BibT_eX]

[DOI]

Hugo Gilbert

Adèle Pass-Lanneau

Proceedings of the Algorithmic Game Theory - 12th International Symposium, 2019

Multistage Knapsack.

[BibT_eX]

[DOI]

Alexandre Teiller

Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science, 2019

Online Multistage Subset Maximization Problems.

[BibT_eX]

[DOI]

Proceedings of the 27th Annual European Symposium on Algorithms, 2019

2018

Purely combinatorial approximation algorithms for maximum k-vertex cover in bipartite graphs.

[BibT_eX]

[DOI]

Discret. Optim., 2018

The Convergence of Iterative Delegations in Liquid Democracy.

[BibT_eX]

[DOI]

Hugo Gilbert

Adèle Pass-Lanneau

CoRR, 2018

Multistage Matchings.

[BibT_eX]

[DOI]

Proceedings of the 16th Scandinavian Symposium and Workshops on Algorithm Theory, 2018

Fair Resource Allocation Over Time.

[BibT_eX]

[DOI]

Sasa Mladenovic

Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, 2018

2017

The Price of Optimum: Complexity and Approximation for a Matching Game.

[BibT_eX]

[DOI]

Algorithmica, 2017

2016

Super-polynomial approximation branching algorithms.

[BibT_eX]

[DOI]

Emeric Tourniaire

RAIRO Oper. Res., 2016

Saving Colors and Max Coloring: Some Fixed-Parameter Tractability Results.

[BibT_eX]

[DOI]

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2016

Parameterized Power Vertex Cover.

[BibT_eX]

[DOI]

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2016

A 0.821-Ratio Purely Combinatorial Algorithm for Maximum k-vertex Cover in Bipartite Graphs.

[BibT_eX]

[DOI]

Proceedings of the LATIN 2016: Theoretical Informatics, 2016

2015

New Results on Polynomial Inapproximabilityand Fixed Parameter Approximability of Edge Dominating Set.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2015

Multi-parameter Analysis for Local Graph Partitioning Problems: Using Greediness for Parameterization.

[BibT_eX]

[DOI]

Algorithmica, 2015

2014

On the approximation of maximum $k$-vertex cover in bipartite graphs.

[BibT_eX]

[DOI]

CoRR, 2014

2013

Exponential approximation schemata for some network design problems.

[BibT_eX]

[DOI]

J. Discrete Algorithms, 2013

Fast algorithms for min independent dominating set.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2013

Fair solutions for some multiagent optimization problems.

[BibT_eX]

[DOI]

Auton. Agents Multi Agent Syst., 2013

Designing Budget-Balanced Best-Response Mechanisms for Network Coordination Games.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Game Theory - 6th International Symposium, 2013

Multi-parameter Complexity Analysis for Constrained Size Graph Problems: Using Greediness for Parameterization.

[BibT_eX]

[DOI]

Proceedings of the Parameterized and Exact Computation - 8th International Symposium, 2013

On Subexponential and FPT-Time Inapproximability.

[BibT_eX]

[DOI]

Proceedings of the Parameterized and Exact Computation - 8th International Symposium, 2013

Truthful Many-to-Many Assignment with Private Weights.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Complexity, 8th International Conference, 2013

2012

Algorithms for dominating clique problems.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2012

Subexponential and FPT-time Inapproximability of Independent Set and Related Problems

[BibT_eX]

[DOI]

Eun Jung Kim

CoRR, 2012

Fast Algorithms for max independent set.

[BibT_eX]

[DOI]

Algorithmica, 2012

Cost allocation protocols for network formation on connection situations.

[BibT_eX]

[DOI]

Proceedings of the 6th International ICST Conference on Performance Evaluation Methodologies and Tools, 2012

Approximating MAX SAT by Moderately Exponential and Parameterized Algorithms.

[BibT_eX]

[DOI]

Emeric Tourniaire

Proceedings of the Theory and Applications of Models of Computation, 2012

New Results on Polynomial Inapproximability and Fixed Parameter Approximability of edge dominating set.

[BibT_eX]

[DOI]

Proceedings of the Parameterized and Exact Computation - 7th International Symposium, 2012

2011

Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2011

The Price of Optimum in a Matching Game.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Game Theory, 4th International Symposium, 2011

Strategy-Proof Mechanisms for Facility Location Games with Many Facilities.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Decision Theory - Second International Conference, 2011

2010

Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs.

[BibT_eX]

[DOI]

J. Discrete Algorithms, 2010

Two-stage stochastic matching and spanning tree problems: Polynomial instances and approximation.

[BibT_eX]

[DOI]

Eur. J. Oper. Res., 2010

A survey on the structure of approximation classes.

[BibT_eX]

[DOI]

Comput. Sci. Rev., 2010

Minimum regulation of uncoordinated matchings

[BibT_eX]

[DOI]

CoRR, 2010

Maximum Independent Set in Graphs of Average Degree at Most Three in O(1.08537n){\mathcal O}(1.08537^n).

[BibT_eX]

[DOI]

Proceedings of the Theory and Applications of Models of Computation, 7th Annual Conference, 2010

A Bottom-Up Method and Fast Algorithms for max independent set.

[BibT_eX]

[DOI]

Proceedings of the Algorithm Theory, 2010

On the Impact of Local Taxes in a Set Cover Game.

[BibT_eX]

[DOI]

Proceedings of the Structural Information and Communication Complexity, 2010

Fast Algorithms for min independent dominating set.

[BibT_eX]

[DOI]

Proceedings of the Structural Information and Communication Complexity, 2010

Strategic Coloring of a Graph.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Complexity, 7th International Conference, 2010

2009

Efficient approximation of min set cover by moderately exponential algorithms.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2009

Probabilistic graph-coloring in bipartite and split graphs.

[BibT_eX]

[DOI]

J. Comb. Optim., 2009

Approximation of min coloring by moderately exponential algorithms.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2009

Weighted coloring on planar, bipartite and split graphs: Complexity and approximation.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2009

Fast Algorithms for Max Independent Set in Graphs of Small Average Degree

[BibT_eX]

[DOI]

CoRR, 2009

Simple and Fast Reoptimizations for the Steiner Tree Problem.

[BibT_eX]

[DOI]

Martin Milanic

Algorithmic Oper. Res., 2009

Efficient Approximation of Combinatorial Problems by Moderately Exponential Algorithms.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Data Structures, 11th International Symposium, 2009

Exact Algorithms for Dominating Clique Problems.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation, 20th International Symposium, 2009

2008

A better differential approximation ratio for symmetric TSP.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2008

Some tractable instances of interval data minmax regret problems.

[BibT_eX]

[DOI]

Oper. Res. Lett., 2008

Some Tractable Instances of Interval Data Minmax Regret Problems: Bounded Distance from Triviality.

[BibT_eX]

[DOI]

Proceedings of the SOFSEM 2008: Theory and Practice of Computer Science, 2008

An O*(1.0977n) Exact Algorithm for max independent set in Sparse Graphs.

[BibT_eX]

[DOI]

Proceedings of the Parameterized and Exact Computation, Third International Workshop, 2008

Single-peaked consistency and its complexity.

[BibT_eX]

[DOI]

Jérôme Lang

Meltem Öztürk

Proceedings of the ECAI 2008, 2008

2007

Improved worst-case complexity for the MIN 3-SET COVERING problem.

[BibT_eX]

[DOI]

Federico Della Croce

Oper. Res. Lett., 2007

Differential approximation of min sat.

[BibT_eX]

[DOI]

Eur. J. Oper. Res., 2007

Approximation of the Quadratic Set Covering problem.

[BibT_eX]

[DOI]

Peter L. Hammer

Discret. Optim., 2007

Polynomial approximation: a structural and operational study.

[BibT_eX]

[DOI]

4OR, 2007

Complexity and Approximation Results for the Connected Vertex Cover Problem.

[BibT_eX]

[DOI]

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2007

Adapting Parallel Algorithms to the W-Stream Model, with Applications to Graph Problems.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2007, 2007

2006

Completeness in approximation classes beyond APX.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2006

On-line models and algorithms for max independent set.

[BibT_eX]

[DOI]

RAIRO Oper. Res., 2006

Reoptimization of Minimum and Maximum Traveling Salesman's Tours.

[BibT_eX]

[DOI]

Proceedings of the Algorithm Theory, 2006

2005

Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness.

[BibT_eX]

[DOI]

Cristina Bazgan

Theor. Comput. Sci., 2005

Proving completeness by logic.

[BibT_eX]

[DOI]

Int. J. Comput. Math., 2005

Weighted Coloring: Further Complexity and Approximability Results.

[BibT_eX]

[DOI]

Proceedings of the Theoretical Computer Science, 9th Italian Conference, 2005

Differential Approximation of min sat, max sat and Related Problems.

[BibT_eX]

[DOI]

Proceedings of the Computational Science and Its Applications, 2005

Probabilistic Coloring of Bipartite and Split Graphs.

[BibT_eX]

[DOI]

Proceedings of the Computational Science and Its Applications, 2005

2004

Weighted Coloring on Planar, Bipartite and Split Graphs: Complexity and Improved Approximation.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation, 15th International Symposium, 2004

Poly-APX- and PTAS-Completeness in Standard and Differential Approximation.

[BibT_eX]

[DOI]

Cristina Bazgan