In practice, the auction algorithm

In practice, the auction algorithm has proved very effective for assignment problems. Computational
studies [BCT91], [BeE88] have shown that it is often substantially faster than its closest competitors,
particularly for sparse problems. The speedup factor typically increases with the problem size. As the
problem density increases the speedup factor tends to decrease and for fully dense problems the auction
algorithm is roughly competitive to methods that combine the primal-dual (or sequential shortest path
method) with an extensive initialization procedure based on the naive auction algorithm of Section 2
[Ber81], [JoV87]. A recent extensive computational study [Cas92] explores the behavior of various auction
algorithms for randomly generated problems with a broad variety of different structures.

ผลลัพธ์ (ไทย) 2:

ในทางปฏิบัติขั้นตอนวิธีการประมูลได้พิสูจน์แล้วว่ามีประสิทธิภาพมากสำหรับปัญหาที่ได้รับมอบหมาย คอมพิวเตอร์ศึกษา [BCT91], [BeE88] แสดงให้เห็นว่ามันมักจะเป็นอย่างมากเร็วกว่าคู่แข่งที่ใกล้เคียงที่สุดของมันโดยเฉพาะอย่างยิ่งสำหรับปัญหาเบาบาง ปัจจัยที่เพิ่มความเร็วมักจะเพิ่มขึ้นกับขนาดของปัญหา ในฐานะที่เป็นความหนาแน่นของปัญหาการเพิ่มขึ้นของปัจจัย speedup มีแนวโน้มที่จะลดลงและปัญหาความหนาแน่นอย่างเต็มที่ประมูลขั้นตอนวิธีการแข่งขันประมาณวิธีการที่รวมที่ครั้งแรกคู่(หรือตามลำดับเส้นทางที่สั้นที่สุดวิธีการ) โดยมีขั้นตอนการเริ่มต้นที่กว้างขวางขึ้นอยู่กับขั้นตอนวิธีการประมูลที่ไร้เดียงสาของมาตรา 2 [Ber81], [JoV87] การศึกษาที่ผ่านการคำนวณอย่างกว้างขวาง [Cas92] สำรวจพฤติกรรมของการประมูลต่างๆขั้นตอนวิธีการสำหรับการแก้ไขปัญหาที่สร้างแบบสุ่มที่มีความหลากหลายในวงกว้างของโครงสร้างที่แตกต่างกัน

ผลลัพธ์ (ไทย) 3:

ในการปฏิบัติงานนี้ได้พิสูจน์แล้วว่ามีประสิทธิภาพมากสำหรับปัญหาการมอบหมายงาน คอมพิวเตอร์ศึกษา bct91
[ ] , [ bee88 ] ได้แสดงให้เห็นว่ามันเป็นบ่อยมากได้เร็วกว่าคู่แข่งใกล้
โดยเฉพาะปัญหาของป่าโปร่ง ปัจจัยการเร่งความเร็วปกติเพิ่มขึ้นตามขนาดของปัญหา .
เป็นปัญหาความหนาแน่นเพิ่มปัจจัยการเร่งความเร็วมีแนวโน้มลดลง และอย่างหนาแน่นปัญหาการประมูล
ขั้นตอนวิธีประมาณที่แข่งขันกับวิธีการรวมดั้งเดิมคู่ ( หรือลำดับวิธีเส้นทางที่สั้นที่สุด
) กับการเริ่มต้นขั้นตอนอย่างละเอียดตามซื่อประมูลอัลกอริทึมของหมวด 2
[ ber81 ] , [ jov87 ]ล่าสุดคอมพิวเตอร์ศึกษาอย่างละเอียด [ cas92 ] สำรวจพฤติกรรมของขั้นตอนวิธีประมูล
ต่างๆสำหรับสุ่มสร้างปัญหากับหลากหลายของโครงสร้างที่แตกต่างกัน