Edge Minimizing the Student Conflict Graph

• URL: http://arxiv.org/abs/2102.06743v1
• Date: Fri, 12 Feb 2021 19:54:44 GMT
• Title: Edge Minimizing the Student Conflict Graph
• Authors: Joshua S. Friedman
• Abstract summary: We give a hybrid approximation sectioning algorithm that minimizes the number of edges in the student conflict graph (SCG) We apply the sectioning algorithm to a highly constrained timetabling model which we specify.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In many schools, courses are given in sections. Prior to timetabling students need to be assigned to individual sections. We give a hybrid approximation sectioning algorithm that minimizes the number of edges (potential conflicts) in the student conflict graph (SCG). We start with a greedy algorithm to obtain a starting solution and then continue with a constraint programming based algorithm (CP-SAT) that reduces the number of edges. We apply the sectioning algorithm to a highly constrained timetabling model which we specify.

Related papers

• Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better [18.121514220195607]
  Cluster deletion is an NP-hard graph clustering objective with applications in computational and social network analysis. We first provide a tighter analysis of two previous approximation algorithms, improving their approximation guarantees from 4 to 3. We show that both algorithms can be derandomized in a surprisingly simple way, by greedily taking a maximum degree in an auxiliary graph and forming a cluster around it.
  arXiv  Detail & Related papers  (2024-04-24T18:39:18Z)
• Graph Cuts with Arbitrary Size Constraints Through Optimal Transport [18.338458637795263]
  We propose a new graph cut algorithm for partitioning graphs under arbitrary size constraints. We solve it using an accelerated proximal GD algorithm which guarantees global convergence to a critical point.
  arXiv  Detail & Related papers  (2024-02-07T10:33:09Z)
• More on greedy construction heuristics for the MAX-CUT problem [8.148355685823521]
  We show that this picture helps to classify the main greedys for the maximum cut problem. All versions of the Sahni-Gonzalez(SG) algorithms could be classified as the Prim class. Various Edge-Contraction(EC) algorithms are of the Kruskal class.
  arXiv  Detail & Related papers  (2023-12-18T02:52:04Z)
• Learning the Positions in CountSketch [49.57951567374372]
  We consider sketching algorithms which first compress data by multiplication with a random sketch matrix, and then apply the sketch to quickly solve an optimization problem. In this work, we propose the first learning-based algorithms that also optimize the locations of the non-zero entries.
  arXiv  Detail & Related papers  (2023-06-11T07:28:35Z)
• Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees [79.59010418610625]
  We study differentially private approximation algorithms for hierarchical clustering. We show strong lower bounds for the problem: that any $epsilon$-DP algorithm must exhibit $O(|V|2/ epsilon)$-additive error for an input dataset. We propose a private $1+o(1)$ approximation algorithm which also recovers the blocks exactly.
  arXiv  Detail & Related papers  (2023-01-31T19:14:30Z)
• Causal Bandits without Graph Learning [28.021500949026766]
  We develop an efficient algorithm for finding the parent node of the reward node using atomic interventions. We extend our algorithm to the case when the reward node has multiple parents.
  arXiv  Detail & Related papers  (2023-01-26T20:27:14Z)
• The Neural-Prediction based Acceleration Algorithm of Column Generation for Graph-Based Set Covering Problems [20.1479227701035]
  We propose an improved column generation algorithm with neural prediction (CG-P) for solving graph-based set covering problems. We leverage a graph neural network based neural prediction model to predict the probability to be included in the final solution for each edge. We evaluate the CG-P algorithm on railway crew scheduling problems and it outperforms the baseline column generation algorithm.
  arXiv  Detail & Related papers  (2022-07-04T13:46:59Z)
• Sample Complexity of Tree Search Configuration: Cutting Planes and Beyond [98.92725321081994]
  State-of-the-art solvers integrate a myriad of cutting-plane techniques to speed up the underlying tree-search algorithm. We prove the first guarantees for learning high-performing cut-selection policies tailored to the instance distribution.
  arXiv  Detail & Related papers  (2021-06-08T00:57:59Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  We introduce a novel algorithm improving over the state-of-the-art along multiple dimensions. We establish minimax optimality for any learning horizon in the special case of non-contextual linear bandits.
  arXiv  Detail & Related papers  (2020-10-23T09:12:47Z)
• Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
  We propose unified algorithms for the important cases of first-order expectations and second-order expectations in edge-factored, non-projective spanning-tree models. Our algorithms exploit a fundamental connection between gradients and expectations, which allows us to derive efficient algorithms.
  arXiv  Detail & Related papers  (2020-08-29T14:58:26Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  We introduce a novel learning problem for dense subgraph discovery. We first propose a edge-time algorithm that obtains a nearly-optimal solution with high probability. We then design a more scalable algorithm with a theoretical guarantee.
  arXiv  Detail & Related papers  (2020-06-24T11:37:33Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.