Approximation Algorithms

Follow this topic Ask about this topic

Momentum

4 papers in the last four weeks, with none the four weeks before. 0.0% of all new papers.

Jul 13Week of Sep 28

Latest papers 41

All topics

Reverse Sequential Proportional Approval Voting Rule: Proportionality and Approximation Guarantees
Sep 28, 2026Georgios PapasotiropoulosElections Majority Voting
University of Warsaw
Pairwise Approximation Can Select the Wrong Multi-Robot Plan
Sep 24, 2026William TeoMulti-Robot Motion Planning Long-Run Coverage Guarantees
MARMoT Lab, Department of Mechanical Engineering, National University of Singapore · NEAR Lab, AI.Robotics Strategic Technology Centre, Singapore Technologies Engineering
Poisson Exchange Beyond Submodularity: Effective Approximation Algorithms for Offline and Online Subset Selection over Matroids
Sep 21, 2026Shi Fu, Youming Qiao, Dacheng Tao +2Submodular Functions Approximation Algorithms
College of Computing and Data Science, Nanyang Technological University, Singapore · Centre for Quantum Software and Information, University of Technology Sydney, Australia · School of Computing and Information Technology, Great Bay University, China
A Sub-4 Approximation for Fair $k$ -Means
Sep 7, 2026Kangke Cheng, Guanlin Mo, Shihong Song +1K-Means Approximation Algorithms
University of Science and Technology of China, Hefei, China · School of Informatics, University of Edinburgh, Edinburgh, UK
Randomized Algorithms for Learning Partitions with Near Optimal Query Complexity in Constant Rounds
Aug 3, 2026Deeparnab Chakrabarty, Aditi Dudeja, David SaulpicO(\Bar{K}\Log N)$Partitioning
Dartmouth College · The Chinese University of Hong Kong (Shenzhen) · CNRS and Universit´e Paris Cit´e
Randomizing the Number of Centers in k-means++
Jul 28, 2026Vaclav RozhonK-Means Approximation Algorithms
Boundary-Adapted PINNs for Elliptic Dirichlet Problems: $H^2(Ω)$ A Priori Error Bounds with Application to Mean Escape Time Computation
Jul 21, 2026Nathanael Tepakbong, Jun Fan, Xiang Zhou +1Parametric Physics-Informed Neural Network Neural Approximations
Department of Data Science, City University of Hong Kong · Department of Mathematics, Hong Kong Baptist University · Department of Mathematics, City University of Hong Kong +1
Graph Partitioning with Demands: Generalized Conductance and its Applications
Jul 14, 2026Michał Szyfelbein, Dariusz DereniowskiMaximum Independent Set Approximation Algorithms
Gda´nsk University of Technology
Hierarchical $\mathcal{F}$ -Clustering: Approximation and Hardness of Clustering into Trees and Bounded Diameter Graphs
Jul 14, 2026Michał Szyfelbein, Dariusz DereniowskiClustering Approximation Algorithms
Gda´nsk University of Technology
The Approximation Ratio for the Risk of Myopic Bayesian Active Learning for Linear Regression
Jul 7, 2026Stephen MussmannPool-Based Active Learning Active Learning
School of Computer Science Georgia Institute of Technology
TSP with Predictions: Heatmap to Tour with Provable Guarantees
Jul 4, 2026Marek Eliáš, Fabrizio Grandoni, Adam Polak +1Salesman Problem Approximation Algorithms
Scalable and Distributed Silhouette Approximation
Jul 2, 2026Ilie Sarpe, Federico Altieri, Andrea Pietracaprina +2Distance Approximation Algorithms
KTH Royal Institute of Technology · University of Padova
The Binary Tree Mechanism is Optimal for Approximate Differentially Private Continual Counting
Jul 1, 2026Konstantina Bairaktari, Kasper Green LarsenStandard Differential-Privacy O(\Bar{K}\Log N)$
Department of Computer Science, Aarhus University.
Recurrent neural networks approximate continuous functions
Jun 18, 2026Valentin Abadie, Clemens Hutter, Helmut BölcskeiNeural Approximations Recurrent Neural Networks
LLM-Guided Test-Time Discovery of Quantum-Chemical Approximation Algorithms
Jun 17, 2026Masaya Hagai, Yuta Suzuki, Tomoya Murata +2Quantum Chemistry Data-Driven Materials Discovery
Lattice Lab, Toyota Motor Corporation · Department of Chemistry, Graduate School of Science, Nagoya University · National Institute of Informatics
Closing the Approximation Gap in Simulation-free Latent SDEs
Jun 15, 2026Henry D. Smith, Brian L. Trippe, Scott W. LindermanStochastic Differential Equations Variational Inference
Stanford University
Learning-Augmented Approximation for Unrelated-Machines Makespan Scheduling
Jun 11, 2026Kaito Baba, Evripidis Bampis, Giorgos MitropoulosApproximation Algorithms Job Shop Scheduling
The University of Tokyo, Tokyo, Japan · Sorbonne Université, CNRS, LIP6, F-75005 Paris, France
A General Framework for Dynamic Consistent Submodular Maximization
Jun 3, 2026Paul Dütting, Federico Fusco, Silvio Lattanzi +3Submodular Functions Approximation Algorithms
1Google Research · 2Dept. of Computer, Control and Management Engineering, Sapienza University of Rome · 3EPFL
TreeFlash: Parallel AR-Approximation for Faster Speculative Decoding
Jun 2, 2026Peer Rheinboldt, Frédéric Berdoz, Roger WattenhoferSpeculative Decoding Flash
ETH Zurich
Variation Spaces for Encoder--Decoder Neural Operators: Approximation and Generalization
May 31, 2026Jia-Qi Yang, Lei ShiNeural Operators Nonlinear Operators
School of Mathematical Sciences and Shanghai Key Laboratory for Contemporary Applied Mathematics, Fudan University, Shanghai 200433, China.
Algorithms with Polynomially-Improved Approximation Factors for the $2 \rightarrow q$ Norm, and Applications
May 24, 2026Samuel B. Hopkins, Stefan TiegelSpectral Norm Approximation Algorithms
MIT
Learning-Augmented Online Scheduling with Parsimonious Preemption
May 22, 2026Mugen Blue, Sungjin Im, Alexander LindermayrSchedulers Preemption
University of California, Santa Cruz, US. · Institut für Mathematik, Technische Universität Berlin, Germany.
An Approximation Algorithm for Graph Label Selection
May 18, 2026Josia John, Simon Meierhans, Maximilian Probst GutenbergApproximation Algorithms Token Budget Allocation
Department of Computer Science, ETH Zurich, Zurich, Switzerland.
Accelerated Relax-and-Round for Concave Coverage Problems
May 7, 2026Matthew Fahrbach, Mehraneh Liaee, Morteza ZadimoghaddamApproximation Algorithms Convex Relaxation
Google Research
On Computing Total Variation Distance Between Mixtures of Product Distributions
May 5, 2026Weiming Feng, Yucheng Fu, Minji Yang +1Approximation Algorithms Mixture Models
School of Computing and Data Science, The University of Hong Kong. · The Institute for Interdisciplinary Information Sciences, Tsinghua University.
Exact and Approximate Algorithms for Polytree Learning
May 5, 2026Juha Harviainen, Frank Sommer, Manuel SorgeBayesian Networks Approximation Algorithms
Department of Computer Science, University of Helsinki, Helsinki, Finland · Institute of Computer Science, Friedrich-Schiller Universität Jena, Jena, Germany · Institute of Logic and Computation, TU Wien, Vienna, Austria
An effective variant of the Hartigan $k$ -means algorithm
Apr 23, 2026François Clément, Stefan SteinerbergerK-Means Approximation Algorithms
Constant-Factor Approximations for Doubly Constrained Fair k-Center, k-Median and k-Means
Apr 17, 2026Nicole Funk, Annika Hennes, Johanna Hillebrand +1K-Means Approximation Algorithms
Department of Informatics, University of Cologne, Germany · Heinrich Heine University Düsseldorf, Faculty of Mathematics and Natural Sciences, Germany · Department of Informatics, University of Bonn, Germany
Unlabeled Multi-Robot Motion Planning with Improved Separation Trade-offs
Mar 19, 2026Tsuri Farhana, Omrit Filtser, Shalev GoldshteinMulti-Robot Motion Planning Approximation Algorithms
Department of Computer Science, Ben Gurion University, Beer Sheva, Israel. · Department of Mathematics and Computer Science, The Open University of Israel, Ra’anana, Israel
Can LLMs Prove Robotic Path Planning Optimality? A Benchmark for Research-Level Algorithm Verification
Mar 19, 2026Zhengbang Yang, Md. Tasin Tazwar, Minghan Wei +1Robot Planning Large Language Model Planning
George Mason University. · Florida Atlantic University.
Equivalence of approximation by networks of single- and multi-spike neurons
Mar 13, 2026Dominik Dold, Philipp Christian PetersenSpiking Neural Networks Time-To-First-Spike
Learning to Approximate Uniform Facility Location via Graph Neural Networks
Feb 13, 2026Chendi Qian, Christopher Morris, Stefanie Jegelka +1Approximation Algorithms Message Passing Neural Networks
RWTH Aachen University, Germany · Technical University of Munich, Germany · Massachusetts Institute of Technology, USA +1
Rational Neural Networks have Expressivity Advantages
Feb 12, 2026Maosen Tang, Alex TownsendActivation Functions Neural Network
Center for Applied Mathematics, Cornell University, United States · Department of Mathematics, Cornell University, United States
Exact and Approximate Range Queries in Ball Mapper
Jan 4, 2026Jay-Anne Bulauan, John Rick ManzanaresApproximate Nearest-Neighbor Search Approximation Algorithms
Independent Researcher · Dioscuri Centre in Topological Data Analysis, Institute of Mathematics of the Polish Academy of Sciences International Environmental Doctoral School of the University of Silesia in Katowice
Sufficient Decision Proxies for Decision-Focused Learning
May 6, 2025Noah Schutte, Grigorii Veviurko, Krzysztof Postek +1Approximation Algorithms
Delft University of Technology · Independent Researcher
Which Spaces can be Embedded in $L_p$ -type Reproducing Kernel Banach Space? A Characterization via Metric Entropy
Oct 14, 2024Yiping Lu, Daozhe Lin, Qiang DuReproducing Kernel Hilbert Spaces Learnability
Industrial Engineering & Management Sciences, Northwestern University · Department of Applied Physics & Applied Mathematics, Columbia University
Faster and Simpler Greedy Algorithm for $k$ -Median and $k$ -Means
Jul 15, 2024Max Dupré la Tour, David SaulpicK-Means Approximation Algorithms
The best approximation pair problem relative to two subsets in a normed space
Mar 27, 2024Daniel Reem, Yair CensorApproximation Algorithms Kernel Hilbert Spaces
Semi-Bandit Learning for Monotone Stochastic Optimization
Dec 24, 2023Arpit Agarwal, Rohan Ghuge, Viswanath Nagarajan +1Stochastic Multi-Armed Bandits Stochastic Optimization
Department of Computer Science & Engineering, Indian Institute of Technology Bombay, Mumbai, India. · Department of Information, Risk, and Operations Management, University of Texas at Austin, Austin, USA. · Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, USA.
Proportionally Representative Clustering
Apr 27, 2023Haris Aziz, Barton E. Lee, Sean Morota Chu +1Clustering Algorithmic Fairness
UNSW Sydney · ETH Zürich · Northwestern University
Deep learning based numerical approximation algorithms for stochastic partial differential equations
Dec 2, 2020Christian Beck, Sebastian Becker, Patrick Cheridito +2Stochastic Differential Equations Neural Approximations
Department of Mathematics, ETH Zurich · School of Data Science and School of Artificial Intelligence,2025 The Chinese University of Hong Kong, Shenzhen (CUHK-Shenhen) · Applied Mathematics: Institute for Analysis and Numerics, University of Münster +1

Sep 28, 2026, cs.GTJ/K move · Enter open · S save

Reverse Sequential Proportional Approval Voting Rule: Proportionality and Approximation Guarantees

Georgios Papasotiropoulos

University of Warsaw

Elections Majority Voting Approximation Algorithms Approximation

Open paper AskPDF arXiv

We study the Reverse Sequential Proportional Approval Voting Rule (RevSeqPAV) in approval-based committee elections. Despite its historical prominence and practical use, its properties and guarantees are much less understood than those of Sequential PAV. We analyze it along two dimensions: proportional representation (measured by Extended Justified Representation, its approximations, and proportionality degree) and approximation of the maximum PAV score of instances. We first establish strong negative results for general, unrestricted election instances and then identify settings in which the rule provides meaningful fairness and optimization guarantees.

Momentum

Related topics

Latest papers 41