Games Site GitHub LinkedIn CV Old Academic Website
Logo Alex's notes
  • Alex Wendland
  • Notes
  • 2-SAT algorithm using SCC
  • 3-SAT is NP-complete
  • A finite tree that has more than one vertex must have at least two leaf vertices
  • A vertex with the highest post order number lies in a source SCC
  • Access control list (ACL) filters
  • Accuracy
  • Action-advantage function (RL)
  • Activation function
  • Acyclic graph
  • Additive Increase Multiplicative Decrease (AIMD)
  • Address Resolution Protocol (ARP)
  • Address space (OS)
  • Adjacency list format (graph)
  • Adjacency matrix format (graph)
  • All linear programmes can be represented in standard form
  • Angur
  • Anonymous Functions
  • Application Programming Interface (API)
  • Arithmetic mean
  • Arithmetic mean is greater than or equal to the geometric mean
  • ARP cache
  • Array (data structure)
  • ARTEMIS
  • Associative array
  • Associativity
  • ASwatch
  • Asynchronous programming
  • Atomic instruction
  • Automatic Repeat Request (ARQ)
  • Autonomous system (AS)
  • Autonomous system number (ASN)
  • B-tree
  • Backward propagation of errors (Back propagation)
  • Backwards compatibility
  • Bagging
  • Balance between library providers and users
  • Balanced cut problem
  • Battle of the sexes
  • Bayes' rule
  • Bayeses optimal classifier
  • Bayesian network
  • Bayesian network if and only if it satisfies the local Markov Property
  • Bellman equation
  • Bellman-Ford algorithm
  • BGP Blackholing
  • BGP Communities
  • BGP Flowspec
  • BGP Hijacking
  • BGP squatting
  • Big-O notation
  • Big-Omega notation
  • Big-Theta notation
  • Binary operation
  • Binary step
  • Binomial coefficient
  • Bipartite graph
  • Bit
  • Bitrate
  • Bitrate adaption
  • Bitwise operations in python
  • Blackholing (BH)
  • Blackholing attack
  • Boolean function
  • Boolean variable
  • Boosting
  • Border gateway protocol (BGP)
  • Breadth-first search (BFS)
  • Bridge
  • Broadcast (networks)
  • Broken tea cup
  • Bucket sort
  • Buddy Allocator
  • Byte
  • Cache
  • Cache coherence
  • Calculate polynomial regression coefficients for MSE
  • Carmichael number
  • Causal consistency
  • Chain Hashing
  • Chain matrix multiply problem
  • Chain rule (probability)
  • Check if a linear programme is solvable
  • Checked exceptions
  • Checking if a linear programme is feasible
  • Checkpointing
  • Checksum
  • Checksum in layer 4
  • Chinese remainder theorem
  • Classes in Python
  • Classification problems
  • Client
  • Client-Server model
  • Clique (graph)
  • Clique of a given size problem
  • Clique of a given size problem is in NP
  • Clique of a given size problem is NP-complete
  • Cliques in G are independent sets in the complement
  • Clustering Problem
  • Cocktail party problem
  • Coding Principles
  • Cohesion
  • Comment conventions
  • Complement graph
  • Complete graph
  • Computational folk theorem
  • Concept
  • Concept class
  • Concurrency
  • Conditional entropy
  • Conditional Independence
  • Conditional probability
  • Conditional variables (Mutex)
  • Congestion control in TCP
  • Conjunctive normal form (CNF)
  • Connected (graph)
  • Connected components (graph)
  • Connection between OSI and IPS models
  • Consistency model
  • Consistent clustering
  • Consistent hashing
  • Consistent learner
  • Consumer Price Index (CPI)
  • Content delivery network (CDN)
  • Context content conclusion (CCC)
  • Context switch (CPU)
  • Conventions
  • Coprime
  • Copy on write (COW)
  • Cost complexity pruning for decision trees (CPP)
  • Count to infinity problem
  • Coupling
  • CPU register
  • Credit assignment problem
  • Cross validation
  • Crossover (genetic algorithms)
  • CRUD API
  • Cut (graph)
  • Cut property
  • Cycle (graph)
  • Cycles in a graph via the DFS tree
  • Data - Object Anti-Symmetry
  • Data structure
  • DDoS reflection and amplification
  • Deadlock
  • Decision tree
  • Declarative Language
  • Default Gateway
  • Degree (graph)
  • Degrees of freedom
  • Demand paging
  • Dependency Inversion Principle (DIP)
  • Dependency Trees (Bayesian Network)
  • Depth-first search (DFS)
  • Descriptor table
  • Design Patterns
  • Device driver
  • DFS for finding strongly connected components
  • DFS to find connected components in an undirected graph
  • DFS to find path in a directed graph
  • DFS to find path in an undirected graph
  • DFS tree (algorithm)
  • Diameter (graph)
  • Difference between an IP and MAC address
  • Dijkstra's algorithm
  • Dimensionality reduction
  • Direct memory access (DMA)
  • Directed acyclic graph (DAG)
  • Directed graph
  • Discounted rewards
  • Distance vector routing algorithms
  • Distributed algorithm
  • Distributed Denial-of-Service (DDoS)
  • Distributed file system (DFS)
  • Distributed shared memory (DSM)
  • DNS censorship
  • DNS injection
  • DNS records
  • Domain Name System (DNS)
  • Dot product
  • DSN-based content delivery
  • Dual linear programme
  • Duplex
  • Dynamic Adaptive Streaming over HTTP (DASH)
  • Dynamic Host Configuration Protocol (DHCP)
  • Dynamic Programming
  • Eager learner
  • Earliest deadline first (EDF)
  • Edge weights
  • Edmonds-Karp algorithm
  • Eigenvector and Eigenvalue
  • Elimination and Nash Equilibrium
  • Encapsulation
  • End to end principle
  • Ensemble learning
  • epsilon-exhausted version space
  • Epsilon-greedy exploration
  • Equivalent tree definitions
  • Ergodic Markov chain
  • Ergodic Markov chain limiting distribution
  • Ergodic Markov chains have a unique stationary distribution
  • Error code
  • Error function (modelling)
  • Error Handling
  • Error rate (modelling)
  • Euclid's rule
  • Euclidean algorithm
  • Euler's theorem (modular arithmetic)
  • Euler's totient function
  • Eulers product formula (totient function)
  • Every min-cut has no flow going backwards along it in a max-flow
  • Every min-cut is at full capacity in a max-flow
  • Evolutionary Architecture model (EvoArch)
  • Exact prefix hijacking
  • Exception
  • Exclusive or
  • Existence of a Fermat witness if and only if composite
  • Existence of Nash equilibrium
  • Expectation Maximisation
  • Expected value
  • Explore exploit dilemma
  • Extended Euclidean algorithm
  • External fragmentation
  • F1 score
  • Fast API
  • Fast retransmit
  • Fast-Flux Service Networks (FFSN)
  • Fermat witness
  • Fermat's little theorem
  • File Transfer Protocol (FTP)
  • Filtering (feature selection)
  • Find connected components in an undirected graph
  • Find path in a directed graph
  • Find path in undirected graph
  • Find strongly connected components for a directed graph
  • Finding rouge networks (FIRE)
  • Finding the maximum likelihood estimation for normally distributed noise is the same as minimising mean squared error
  • Finite Markov Decision Process
  • Firewall
  • First in first out (FIFO) queue
  • First-class object
  • Flow
  • Flow control in TCP
  • Flow network
  • Flows are maximal if there is no augmenting path
  • Fold (cross validation)
  • Folk Theorem
  • Ford-Fulkerson Algorithm
  • Forest (graph)
  • Formatting conventions
  • Fourier Matrix
  • Fragmentation
  • Frame (networks)
  • Function
  • Function codomain
  • Function conventions
  • Function domain
  • Function image
  • Functions in Python
  • Game theory
  • Gateway
  • Gaussian kernel (SVM)
  • Genetic algorithm (meta)
  • Geometric mean
  • Gini index
  • Go back N
  • Gradient decent
  • Graph
  • Graph representations
  • Great Firewall of China (GFW)
  • Greatest common divisor
  • Gridworld
  • Grim trigger strategy
  • Halting problem
  • Happens with high probability
  • Hardware protection levels
  • Hash function
  • Hash table
  • Haussler Theorem
  • Head of line (HOL) blocking
  • Heap (OS)
  • Hill climbing
  • Host (networks)
  • Hot potato routing
  • How post order relates to strongly connected components
  • HTTP redirection
  • Hub
  • Hyper Text Transfer Protocol (HTTP)
  • Hyperbolic tangent (tanh)
  • Hyperplane
  • Hypertext Transfer Protocol Secure (HTTPS)
  • If a point in a linear programme has equal objective function to a point in its dual linear programme they are both optimal
  • If two variables are independent conditional entropy excludes the dependent
  • If two variables are independent joint entropy is additive
  • Image Segmentation
  • Image segmentation by max flow
  • Imperative Programming
  • Impossibility Theorem
  • Imposters syndrome
  • Imposture attack (IM)
  • Increasing sequence
  • Incremental learning
  • Independent component analysis
  • Independent events
  • Independent identically distributed samples
  • Independent set (graph)
  • Independent set of a given size
  • Independent set of a given size is in NP
  • Independent set of a given size is NP-complete
  • Indicator function
  • Induced subgraph
  • Inductive bias
  • Infeasible linear programme
  • Inference
  • Information entropy
  • Instance-based learning
  • Integer linear programming is NP-hard
  • Integer linear programming problem
  • Integrated Memory Controller (IMC)
  • Inter-process communication (IPC)
  • Interdomain routing
  • Interface
  • Interface definition language (IDL)
  • Interior gateway protocol (IGP)
  • Internal fragmentation
  • Internet
  • Internet engineering task force (IETF)
  • Internet Exchange Points (IXPs)
  • Internet Protocol (IP)
  • Internet Protocol (IPv4)
  • Internet Protocol Stack (IPS) 4 layers
  • Internet Protocol Stack (IPS) 5 layers
  • Internet protocol stack hourglass shape
  • Internet Service Provider (ISP)
  • Intradomain routing
  • Inverse of the Fourier matrix
  • Inverted page tables (IPT)
  • IP Anycast
  • Iris
  • Irreducible
  • Irreducible error
  • Irreducible Markov chain
  • Irrelevant feature
  • Iterative algorithms
  • Iterative Dichotomiser 3 (ID3)
  • Joint distribution
  • Joint Entropy
  • k-colourings problem (graphs)
  • k-means clustering
  • k-nearest neighbour
  • k-SAT is in NP
  • k-SAT is NP-complete for k greater than or equal to 3
  • k-satisfiability problem (k-SAT problem)
  • Kernel
  • Kernel trick
  • Knapsack Problem
  • Knapsack problem (without repetition)
  • Knapsack-search (without replacement)
  • Knapsack-search is NP
  • Knapsack-search is NP-complete
  • Kruskal's algorithm
  • Kullback–Leibler divergence
  • Lambda functions
  • Layer 1 Physical
  • Layer 2 Data Link
  • Layer 3 Network
  • Layer 4 Transport
  • Layer 5 Session
  • Layer 6 Presentation
  • Layer 7 Application
  • Lazy learner
  • Leaf (graph)
  • Learning rate convergence
  • Least-recently used (LRU)
  • Length of a probability
  • Linear dimensionality reduction
  • Linear programme
  • Linear programme standard form
  • Linear programming problem
  • Linear regression
  • Linearly separable
  • Link-state routing algorithms
  • Linked lists
  • Local Markov property
  • Logarithms
  • Logging in python
  • Logical and
  • Logical OR
  • Loop (graph)
  • MAC address
  • Machine Learning
  • Man-in-the-middle attack (MM)
  • Many-one reduction (problem)
  • Margin for a linear separator
  • Marginalisation (probability)
  • Markdown
  • Markov chain
  • Markov decision process
  • Markup Language
  • Masters theorem
  • Matrix
  • Max clique problem (graph)
  • Max clique problem is NP-hard
  • Max flow problem
  • Max independent set problem (graph)
  • Max independent set problem is NP-hard
  • Max-flow min-cut Theorem
  • Max-k-exact-satisfiability problem
  • Max-SAT is NP-hard
  • Max-SAT random approximation algorithm
  • Max-Satisfiability Problem
  • Maximum a posteriori probability estimate (MAP)
  • Maximum likelihood estimation (MLE)
  • Mean squared error (MSE)
  • Memory allocator
  • Memory controller
  • Memory frame
  • Memory Management Unit (MMU)
  • Memory page
  • Memory segment
  • Memory segmentation
  • Middleboxes
  • MIMIC (meta)
  • MIMIC by dependency trees
  • Min st-cut problem
  • Min-heap
  • Minimax-Q
  • Minimum Spanning Tree problem (MST)
  • Minimum Spanning Tree problem is in NP
  • Minimum vertex cover problem
  • Minimum vertex cover problem is NP-hard
  • Minmax decision
  • Minmax profile
  • Mistake bound
  • Mixed strategy
  • Model-based reinforcement learning
  • Modelling bias
  • Modelling framework
  • Modelling paradigm
  • Modular arithmetic
  • Modular exponent algorithm
  • Modular exponent problem
  • Modular inverse algorithm (extended Euclidean algorithm)
  • Modular inverse problem
  • Modular multiplicative inverse existence
  • Monitors
  • MPEG-DASH
  • Multi-level page tables
  • Multi-processing
  • Multi-threading
  • Multiplexing
  • Multiprotocol label switching (MPLS)
  • Mutability
  • Mutability in Python
  • Mutation (genetic algorithms)
  • Mutex
  • Mutual information
  • Mutual information is symmetric
  • Naive Bayes classifier
  • Namespaces
  • Naming conventions
  • Nash equilibrium
  • Neighbourhood (graph)
  • NeoVim Cheat Sheet
  • Network
  • Network Address Translation (NAT)
  • Network file system (NFS)
  • Network mask
  • Neural network
  • Node (IPv6)
  • Non-trivial Fermat witnesses are dense
  • Nondeterministic Polynomial time (NP)
  • Normal distribution
  • Northbridge Memory Controller
  • NP-Complete
  • NP-hard
  • Object
  • Objective function
  • Occam's razor
  • Ones complement
  • Open Closed Principle (OCP)
  • Open Shortest Path First (OSPF)
  • Open Systems interconnection (OSI) model
  • OpenFlow
  • Operating system (OS)
  • Optimisation problem
  • Optimistic exploration
  • Optimum play exists for 2-player zero-sum games with perfect information
  • Overfitting
  • P equals NP or P not equals NP
  • p-value
  • PAC learnable bound with VC-dimension
  • PAC-learnable if and only if finite VC dimension
  • Packets
  • Page rank
  • Page rank algorithm
  • Page table
  • Page table entry
  • Paging system
  • Pairwise coprime
  • Palindrome
  • Parallelisation
  • Partition (set)
  • Passing variables to a function
  • Path (graph)
  • Pavlov strategy
  • PCI Express (PCIe)
  • Peer distributed application
  • Peer-peer model
  • Perceptron (neural network)
  • Perceptron rule
  • Perfect information
  • Periodic Markov chain
  • Periodic state (markov chain)
  • Peripheral Component Interconnect (PCI)
  • Physical Frame Number (PFN)
  • Physical memory
  • Pipe
  • Plausible threat
  • Policy (MDP)
  • Policy Iteration (MDP)
  • Polymorphism
  • Polynomial kernel (SVMs)
  • Polynomial regression
  • Polynomial time
  • Polynomial time is a subset of NP-complete
  • Polysemy
  • Port
  • Portable operating system interface (POSIX)
  • POSIX threads (PThreads)
  • Postorder traversal
  • Pre-commit hooks
  • Pre-pruning decision trees
  • Precision
  • Prediction
  • Preference bias
  • Preorder traversal
  • Prim's algorithm
  • Prime
  • Principle component analysis
  • Prisoner's dilemma
  • Probability distribution
  • Probably approximately correct learnable (PAC)
  • Procedural Programming
  • Process
  • Process control block (PCB)
  • Process Identification (PID)
  • Process modes
  • Product of roots of unity
  • Program counter (PC)
  • Programmed IO (PIO)
  • Programming paradigms
  • Proper vertex colouring
  • Protocol (networks)
  • Pseudo devices
  • Pseudo-header
  • Pseudo-polynomial time
  • Pure strategy
  • Python Built-in Functions
  • Pythonic
  • Q-function (RL)
  • Q-learning
  • Quality function (RL)
  • Quantization
  • Quick sort
  • Race condition
  • Random Access Memory (RAM)
  • Random component analysis
  • Reader-writer locks
  • Recall
  • Rectified linear unit (ReLU)
  • Recursion
  • Refactored
  • Reference counting in Python
  • Regression problems
  • Reinforcement learning
  • Reliable transmission of TCP messages
  • Remote direct memory access (RDMA)
  • Remote Procedure Calls (RPC)
  • Repeater
  • Request for Comments (RFC)
  • Residual Network (flow)
  • REST API
  • Restart hill climbing
  • Restriction Bias
  • Result types
  • Retail Price Index (RPI)
  • Return (RL)
  • Reverse directed graph
  • Reversible Markov chain
  • Rich clustering
  • Rivest-Shamir-Adleman algorithm (RSA algorithm)
  • Rooted tree
  • Round robin DNS (RRDNS)
  • Round trip time (RTT)
  • Route summarization
  • Router
  • Router (IPv6)
  • Routing
  • Routing Information Protocol (RIP)
  • Routing table
  • Rudrata cycle
  • Rudrata cycle problem
  • Rudrata path
  • Rudrata path problem
  • Run time complexity
  • Sample complexity
  • SAT is NP-complete
  • Satisfiability problem (SAT problem)
  • SBRI model
  • Scale-invariant clustering
  • Search problems
  • Secure Socket Layer (SSL)
  • Security region
  • Segment
  • Semaphores
  • Semi-wall stochastic game
  • Separation of concerns (SoC)
  • Sequence
  • Sequential consistency
  • Server
  • Session Initiation Protocol (SIP)
  • Side effect
  • Sigmoid function
  • Sigmoid kernel (SVM)
  • Sign function
  • Signed or unsigned integers
  • Simple Mail Transfer Protocol (SMTP)
  • Simplex method (linear programme)
  • Simulated Annealing
  • Simulated annealing ending probability
  • Single linkage clustering
  • Single Responsibility Principle (SRP)
  • Singleton
  • Slab allocator
  • Socket
  • Soft clustering
  • Software defined networks (SDN)
  • SOLID principles
  • Sorting problem
  • Spanning subgraph
  • Spanning Tree Protocol (STP)
  • Special case pattern
  • Special functions
  • Spinlocks
  • Spoofing
  • Spurious wakeups
  • st-cut
  • Stack (OS)
  • Stack Pointer (SP)
  • Standard deviation
  • Start and end point bias
  • Stationary distribution (Markov Chains)
  • Step function
  • Step function methods
  • Stirling's approximation
  • Stochastic games
  • Stochastic matrix
  • Stop and wait ARQ
  • Strict consistency
  • Strictly dominated strategy
  • Strong duality theorem (linear programme)
  • Strong duality theorem optimum (linear programme)
  • Strongly connected (directed graphs)
  • Strongly connected component graph (directed graph)
  • Strongly connected components (directed graphs)
  • Strongly relevant feature
  • Sub-prefix hijacking
  • Subgame perfect
  • Subgraph
  • Subnets
  • Subsequence
  • Subset-sum problem
  • Subset-sum problem is in NP
  • Subset-sum problem is NP-complete
  • Substring
  • Sum of roots of unity
  • Supervised learning
  • Support vector machines (SVM)
  • Switch
  • Switching
  • Symmetric Markov chain
  • Symmetric Markov chains have a uniform stationary distribution
  • Synchronization
  • Synonymy
  • System call
  • Taking the reverse respects going to the strongly connected component graph
  • TCP 3 way handshake
  • TCP connection teardown
  • TCP CUBIC
  • TCP Reno
  • Test Driven Development (TDD)
  • Testing conventions
  • Testing data
  • The 5S Philosophy
  • The curse of dimensionality
  • The dual dual linear programme is the original linear programme
  • The flow across an st-cut is equal to the value of the flow itself
  • The Halting problem is undecidable
  • The k-colourings problem is in NP
  • The k-colourings problem is NP-complete
  • The Law of Demeter
  • The perceptron rule using binary step converges in finite time if the dataset is linearly separable
  • The Satisfiability problem is in NP
  • The strongly connected component graph is a DAG
  • The strongly connected components are the same in a directed graph and its reverse
  • Thread
  • Tit for Tat
  • Topological sorting (DAG)
  • Traffic Engineering Framework
  • Traffic Scrubbing Service
  • Train Wrecks
  • Training data
  • Training error
  • Trampolining
  • Transforming discrete input for regression
  • Transitions (MDP)
  • Translation Lookaside Buffer (TLB)
  • Transmission control in TCP
  • Transmission Control Protocol (TCP)
  • Transport Layer Security (TLS)
  • Trap instruction
  • Traveling salesman problem
  • Travelling salesman problem (search)
  • Tree (graph)
  • Trie
  • True error
  • Two's complement
  • Type-0 hijacking
  • Type-N hijacking
  • Type-U hijacking
  • Unbounded linear programme
  • Unbounded linear programmes have infeasible duals
  • Undecidable problem
  • Underfitting
  • Unicast
  • Uniform distribution
  • Uniqueness of inverses
  • Unsupervised learning
  • Useful feature
  • User Datagram Protocol (UDP)
  • Using multiple git profiles
  • Value function (RL)
  • Value iteration (MDP)
  • Vapnik-Chervonenkis dimension
  • Variables in python
  • Variance
  • Version space
  • Vertex Colouring
  • Vertex cover
  • Vertex cover if and only if the complement is an independent set
  • Vertex cover of a given size
  • Vertex cover of a given size is NP
  • Vertex cover of a given size is NP-complete
  • Vertex degree sum in a graph
  • Virtual Local Area Networks (VLAN)
  • Virtual machine monitor (VMM)
  • Virtual memory
  • Virtual page number (VPN)
  • Virtualization
  • Voice over IP (VoIP)
  • Weak consistency
  • Weak duality theorem (linear programme)
  • Weak learner
  • Weakly relevant feature
  • Webgraph
  • When to Use Error Codes and Exceptions
  • Wrap 3rd party libraries
  • Wrapping (feature selection)
  • Zero-sum game

# Linear programming problem

Last edited: 2026-02-05

# Statement

Linear programme problem

Given a linear programme what is an $x \in \mathbb{R}^n$ that achieves an optimal solution if it exists.

# Solutions

  • Ellipsoid method
  • Interior-point method
  • Simplex method

# Theory

# Related problems

  • Max flow problem
  • Integer linear programming problem
Made by Alex powered by Hugo