Frontiers of Algorithmics

This book LNCS15828 constitutes the refereed proceedings of the 19th International Joint Conference on Theoretical Computer Science-Frontier of Algorithmic Wisdom (IJTCS-FAW 2025), consisting of the 19th International Conference on Frontier of Algorithmic Wisdom (FAW) and the 6th International Joint Conference on Theoretical Computer Science (IJTCS), held in Paris, France, during June 30July 2, 2025.

The 28 full papers and 2 short papers were carefully reviewed and selected from 63 submissions. The proceedings focuses on Frontiers of Algorithmic Wisdom; Block-chain, Distributed Computing, Multi-Agents; Game Theory, Algorithmic Game Theory, Machine Learning, Electronic Commerce.

Klappentext

Domination in Diameter Two Graphs and the 2 Club Cluster Vertex Deletion Parameter.- $k$-Universality of Regular Languages Revisited.- Comparing the Hardness of Online Minimization and Maximization Problems with Predictions.- Complexity Classes for Online Problems with and without Predictions.- Scheduling with Testing: Competitive Algorithms for Minimizing the Total Weighted Completion Time in the Adversarial Model.- Mixed Graph Covering with Target Constraints.- Multiplication of 0-1 matrices via clustering.- From MAXCUT to MAXNAESAT: Elegant Proofs and Algorithmic Advances.- Exact Algorithms for the Maximum $k$-Balanced Weighted Biclique Problem.- Approximation Algorithms for Individual Preference Facility Location.- The online power cover problem on a line.- The Subinterval Cover Problem.- Oblivious Robots Under Round Robin: Gathering on Rings.- Finding a Set of Long Common Substrings with Repeats from m Input Strings.- A LP-rounding based algorithm for soft capacitated facility location problem with submodular penalties.- Less-excludable Mechanism for DAOs in Public Good Auctions.- TBDS: Transaction-Based Data Sharing.- Pure Nash Equilibria of Weighted Picking Sequence Protocol is WEF1 for Two Agents.- A Comparative Study of Waitlist Mechanisms: Deferral Versus Pay-Per-Offer.- Optimal Repurchasing Contract Design for Efficient Utilization of Computing Resources.- Characterizing Strategyproofness Through Score Functions in Voting Mechanisms.- Minimizing Blocking Agents for Stable Matching with Partial Approval Information.- The Capacity-Constrained Facility Location Problem with Ordinal Preferences: Algorithmic and Mechanism Design Perspectives.- Regularized Minimax-V Learning for Solving Randomly Terminating Two-player Zero-sum Markov Games.- Improved Approximation of Maximin Share Fair Allocation under Generalized Assignment Constraints.- Optimal Hiring Strategy in Auction-Based Crowdsourcing Systems.- Large-Scale Contextual Market Equilibrium Computation through Deep Learning.- Fair Value Distribution in Cooperative Committee Election.- A Payoff-Based Policy Gradient Method in Stochastic Games with Long-Run Average Payoffs.- Mechanism Design for Auctions with Externalities on Budgets.

Inhalt

Domination in Diameter Two Graphs and the 2 Club Cluster Vertex Deletion Parameter.- $k$-Universality of Regular Languages Revisited.- Comparing the Hardness of Online Minimization and Maximization Problems with Predictions.- Complexity Classes for Online Problems with and without Predictions.- Scheduling with Testing: Competitive Algorithms for Minimizing the Total Weighted Completion Time in the Adversarial Model.- Mixed Graph Covering with Target Constraints.- Multiplication of 0-1 matrices via clustering.- From MAXCUT to MAXNAESAT: Elegant Proofs and Algorithmic Advances.- Exact Algorithms for the Maximum $k$-Balanced Weighted Biclique Problem.- Approximation Algorithms for Individual Preference Facility Location.- The online power cover problem on a line.- The Subinterval Cover Problem.- Oblivious Robots Under Round Robin: Gathering on Rings.- Finding a Set of Long Common Substrings with Repeats from m Input Strings.- A LP-rounding based algorithm for soft capacitated facility location problem with submodular penalties.- Less-excludable Mechanism for DAOs in Public Good Auctions.- TBDS: Transaction-Based Data Sharing.- Pure Nash Equilibria of Weighted Picking Sequence Protocol is WEF1 for Two Agents.- A Comparative Study of Waitlist Mechanisms: Deferral Versus Pay-Per-Offer.- Optimal Repurchasing Contract Design for Efficient Utilization of Computing Resources.- Characterizing Strategyproofness Through Score Functions in Voting Mechanisms.- Minimizing Blocking Agents for Stable Matching with Partial Approval Information.- The Capacity-Constrained Facility Location Problem with Ordinal Preferences: Algorithmic and Mechanism Design Perspectives.- Regularized Minimax-V Learning for Solving Randomly Terminating Two-player Zero-sum Markov Games.- Improved Approximation of Maximin Share Fair Allocation under Generalized Assignment Constraints.- Optimal Hiring Strategy in Auction-Based Crowdsourcing Systems.- Large-Scale Contextual Market Equilibrium Computation through Deep Learning.- Fair Value Distribution in Cooperative Committee Election.- A Payoff-Based Policy Gradient Method in Stochastic Games with Long-Run Average Payoffs.- Mechanism Design for Auctions with Externalities on Budgets.