การออกแบบเครือข่ายที่เหมาะสมที่สุดเป็นปัญหาในการเพิ่มประสิทธิภาพเชิงการจัดเรียง (combinatorial optimization ) เป็นการแสดงภาพนามธรรมของปัญหาที่รัฐและเทศบาลต้องเผชิญเมื่อวางแผนเครือข่ายถนน โดยกำหนดชุดสถานที่ที่จะเชื่อมต่อกันด้วยถนน เป้าหมายคือการมีระยะทางในการเดินทางที่สั้นที่สุดระหว่างจุดสองจุดทุก ๆ จุด โดยเฉพาะอย่างยิ่ง เป้าหมายคือการลดผลรวมของระยะทางที่สั้นที่สุด โดยผลรวมนั้นคำนวณจากทุกคู่ของจุด สำหรับแต่ละสองสถานที่ จะมีตัวเลขที่แสดงถึงต้นทุนในการสร้างถนนตรงระหว่างกัน จะต้องมีการตัดสินใจว่าจะสร้างถนนสายใดบ้างด้วยงบประมาณที่จำกัด

ข้อมูลนำเข้าสำหรับปัญหาการออกแบบเครือข่ายที่เหมาะสมที่สุดคือ กราฟถ่วงน้ำหนักG = (V,E) โดยที่น้ำหนักของแต่ละขอบ (u,v) ในกราฟแสดงถึงต้นทุนในการสร้างถนนจาก u ไปยัง v และงบประมาณ B

เครือข่ายที่เป็นไปได้คือเซตย่อย S ของ E โดยที่ผลรวมของ w(u,v) สำหรับทุก (u,v) ใน S มีค่าไม่เกิน B และมีเส้นทางระหว่างทุกโหนด u และ v (นั่นคือ S ประกอบด้วยต้นไม้แผ่คลุมของ G)

สำหรับแต่ละเครือข่ายที่เป็นไปได้Sต้นทุนรวมของ S คือผลรวมของความยาวของเส้นทางที่สั้นที่สุดจาก u ไปยัง v โดยใช้เฉพาะขอบใน S เท่านั้น สำหรับทุกคู่ (u,v) ใน E เป้าหมายคือการค้นหาเครือข่ายที่เป็นไปได้ที่มีต้นทุนรวมต่ำที่สุด

Johnson, Lenstra และ Kan พิสูจน์ว่าปัญหานี้เป็นNP-hardแม้แต่ในกรณีง่ายๆ ที่น้ำหนักขอบทั้งหมดเท่ากันและงบประมาณจำกัดตัวเลือกให้ครอบคลุมเฉพาะต้นไม้^{[ 1 ]}

Dionne และ Florian ศึกษา อัลกอริทึม การแบ่งสาขาและขอบเขตและแสดงให้เห็นว่าอัลกอริทึมเหล่านี้ทำงานได้ในเวลาที่เหมาะสมสำหรับข้อมูลป้อนเข้าขนาดกลาง แต่ไม่ได้ทำงานกับข้อมูลป้อนเข้าขนาดใหญ่ ดังนั้นพวกเขาจึงนำเสนออัลกอริทึมการประมาณค่า แบบฮิวริสติ ก^{[ 2 ]}

Anshelevic, Dasgupta, Tardos และ Wexler ศึกษาเกมการออกแบบเครือข่าย โดยที่ตัวแทนแต่ละคนมีชุดเทอร์มินัลและต้องการสร้างเครือข่ายที่เทอร์มินัลของตนเชื่อมต่อกัน แต่จ่ายให้น้อยที่สุด พวกเขาศึกษาปัญหาการคำนวณในการตรวจสอบว่าสมดุลแนชมีอยู่หรือไม่ สำหรับบางกรณีพิเศษ พวกเขานำเสนออัลกอริทึมเวลาพหุนามที่ค้นหาสมดุลแนชโดยประมาณ(1+ε) ^{[ 3 ]}

Boffey และ Hinxman นำเสนอ วิธี การฮิวริสติกและแสดงให้เห็นว่าวิธีการนี้ให้ผลลัพธ์ที่มีคุณภาพสูง พวกเขายังศึกษาถึงวิธีการแก้ปัญหาโดยใช้การแบ่งแยกและขอบเขต และประเมินผลกระทบของการประมาณค่าต่างๆ เมื่อคำนวณขอบเขตล่าง นอกจากนี้ พวกเขายังขยายปัญหาไปสู่เครือข่ายที่มีต้นทุนการก่อสร้างลิงก์ที่ไม่เป็นสัดส่วนกับความยาว และมีความต้องการการเดินทางที่ไม่เท่ากันทั้งหมด^{[ 4 ]}

• การวางแผนและการออกแบบเครือข่าย
• ต้นไม้แผ่ขยายที่มีต้นทุนการกำหนดเส้นทางต่ำสุด – ปัญหาที่คล้ายกันซึ่งเซตที่เลือกจะต้องเป็นต้นไม้แผ่ขยาย